QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695891#5433. Absolute DifferenceDiverbeeWA 0ms4048kbC++142.5kb2024-10-31 21:00:072024-10-31 21:00:28

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 21:00:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4048kb
  • [2024-10-31 21:00:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;


ld qi(pair<ld,ld> a,pair<ld,ld> b){
    if(a>b)swap(a,b);

    if(a==b){
        return (a.second-a.first)*1.0/3;
    }
    if(a.first==a.second){
        return abs((b.first+b.second)*1.0/2 - a.first);
    }
    if(b.first==b.second){
        return abs(b.first - (a.first+a.second)/2);
    }

    if(b.first>=a.second){
        return ((b.second + b.first) - (a.second + a.first))*1.0/2;
    }

    if(b.second<=a.second){//包含
        ld u = b.first - a.first;
        ld v = b.second - b.first;
        ld w = a.second - b.second;
        ld res = 0;
        res += (v/2+u/2)*u + v*(v/3) + w*(w/2 + v/2);
        res /= (u+v+w);
        return res;
    }else{//相交
        ld u = b.first - a.first;
        ld v = a.second - b.first;
        ld w = b.second - a.second;
        ld res = 0;
        res = u*(v+w+u)/2 + v*(v*v/3+w*(w+v)/2)/(v+w);
        res /= (u+v);
        return res;
    }
}
ll ssm1=0,ssm2 = 0;

ld quan1(pair<int,int> p){
    if(ssm1)return p.second- p.first;
    else return 1;
}

ld quan2(pair<int,int> p){
    if(ssm2)return p.second- p.first;
    else return 1;
}

signed main(){
    int n,m;cin>>n>>m;
    vector<pair<ld,ld> > vc1(n);
    vector<pair<ld,ld> > vc2(m);

    for(auto &it:vc1)cin>>it.first>>it.second,ssm1+=it.second - it.first;
    for(auto &it:vc2)cin>>it.first>>it.second,ssm2+=it.second - it.first;
    sort(vc1.begin(),vc1.end());
    sort(vc2.begin(),vc2.end());

    ld zq1=0,zq2=0;
    for(auto it:vc1)zq1+=quan1(it);
    for(auto it:vc2)zq2+=quan2(it);

    ld ans =0;
    ld sm1=0,sm2=0;
    ld he1 = 0,he2=0;
    for(auto it:vc2)sm2 += quan2(it)*(it.second+it.first)/2,he2+=quan2(it);
    int p = 0,q=0;
    for(auto it:vc1){
        while (p<vc2.size()&&vc2[p].second<=it.first){
            sm1 += quan2(vc2[p])*(vc2[p].second + vc2[p].first)/2;
            he1 += quan2(vc2[p]);
            p++;
        }
        while(q<vc2.size()&&vc2[q].first<=it.second){
            sm2 -= quan2(vc2[q])*(vc2[q].second + vc2[q].first)/2;
            he2 -= quan2(vc2[q]);
            q++;
        }
        ld uu = 0;
        uu = (it.second+it.first)/2*he1 - sm1;
        uu += sm2 - (it.second + it.first)/2*he2;

        for(int i = p;i<q;++i){
            uu += quan2(vc2[p])*qi(it,vc2[i]);
        }
        uu/=zq2;
        ans += quan1(it)/zq1*uu;
    }

    cout<<fixed<<setprecision(12)<<ans;

    return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

1 1
0 1
0 1

output:

0.333333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

1 1
0 1
1 1

output:

0.500000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4048kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000000

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3812kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

6717.114576231945

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '6717.1145762', error = '0.0000004'