QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695972#5433. Absolute DifferenceDiverbeeWA 2ms4044kbC++142.7kb2024-10-31 21:12:152024-10-31 21:12:23

Judging History

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

  • [2024-10-31 21:12:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4044kb
  • [2024-10-31 21:12:15]
  • 提交

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<ld,ld> p){
    if(ssm1)return p.second- p.first;
    else return 1;
}

ld quan2(pair<ld,ld> 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);

    vector<ld > q1(n);
    vector<ld > q2(m);

    for(int i = 0 ; i < n ;++i)q1[i] = quan1(vc1[i])/zq1;
    for(int i = 0 ; i < m ;++i)q2[i] = quan2(vc2[i])/zq2;

    ld ans =0;
    ld sm1=0,sm2=0;
    ld he1 = 0,he2=0;
    for(int i = 0 ; i < m ;++i){
        auto it = vc2[i];
        sm2 += q2[i]*(it.second+it.first)/2;
        he2 += q2[i];
    }
    int p = 0,q=0;
    for(int j = 0 ; j < n ; ++j){
        auto it = vc1[j];
        while (p<vc2.size()&&vc2[p].second<=it.first){
            sm1 += q2[p]*(vc2[p].second + vc2[p].first)/2;
            he1 += q2[p];
            p++;
        }
        while(q<vc2.size()&&vc2[q].first<=it.second){
            sm2 -= q2[q]*(vc2[q].second + vc2[q].first)/2;
            he2 -= q2[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 += q2[i]*qi(it,vc2[i]);
        }
        ans += q1[j]*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: 3872kb

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: 3872kb

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: 3944kb

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: 3868kb

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: 4044kb

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: 3872kb

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: 3816kb

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: 3908kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

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

Test #9:

score: 0
Accepted
time: 2ms
memory: 4000kb

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.117145739454

result:

ok found '6717.117145739', expected '6717.117145739', error '0.000000000'

Test #10:

score: -100
Wrong Answer
time: 2ms
memory: 3900kb

input:

1000 1000
-5010 -4999
-2128 -2113
-5798 -5765
705 713
-3956 -3938
-5308 -5307
6759 6772
-772 -770
-860 -859
2308 2323
-5500 -5500
5140 5177
-6747 -6733
7509 7511
8864 8870
-6382 -6374
1901 1904
-5763 -5760
3019 3027
2962 2963
-314 -301
-222 -203
-726 -724
-62 -58
-1203 -1195
-5216 -5215
-4298 -4292
...

output:

6682.578597814208

result:

wrong answer 1st numbers differ - expected: '6682.5811275', found: '6682.5785978', error = '0.0000004'