QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#150619 | #5433. Absolute Difference | tanao | WA | 2ms | 7780kb | C++14 | 1.7kb | 2023-08-25 21:59:07 | 2023-08-25 21:59:09 |
Judging History
answer
//https://codeforces.com/gym/104160
#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define MAX_N 200010
using namespace std;
struct node
{
double l,r;
}a[MAX_N],b[MAX_N];
bool cmp(node a,node b)
{
return a.l<b.l;
}
double sum[MAX_N];
double cal(node x,node y)
{
if(x.l>y.l)swap(x,y);
if(y.r>x.r)
{
double a=y.l-x.l,c=x.r-y.l,b=y.r-x.r;
return ((a+b+c)*(a+b+c)*(a+b+c)-a*a*a-b*b*b+c*c*c)/(6*(a+c)*(b+c));
}
else
{
double a=y.l-x.l,b=y.r-y.l,c=x.r-y.r;
return (3*a*a+3*a*b+3*c*c+3*c*b+2*b*b)/(6*(a+b+c));
}
}
double lena[MAX_N],lenb[MAX_N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i].l>>a[i].r,a[i].r+=1e-10;
for(int i=1;i<=m;++i)cin>>b[i].l>>b[i].r,b[i].r+=1e-10;
sort(a+1,a+n+1,cmp);
sort(b+1,b+m+1,cmp);
for(int i=1;i<=n;++i)lena[i]=lena[i-1]+a[i].r-a[i].l;
for(int i=1;i<=m;++i)lenb[i]=lenb[i-1]+b[i].r-b[i].l;
for(int i=1;i<=m;++i)sum[i]=sum[i-1]+(b[i].l+b[i].r)/2*(lenb[i]-lenb[i-1]);
int lp=0,rp=1;
double ans=0;
for(int i=1;i<=n;++i)
{
while(lp<m&&b[lp+1].r<=a[i].l)lp++;
while(rp<=m&&b[rp].l<a[i].r)rp++;
// cout<<lp<<" "<<rp<<"|"<<(a[i].l+a[i].r)/2*lp-sum[lp]<<" "<<(sum[m]-sum[rp-1]-(double)(a[i].l+a[i].r)/2*(m-rp+1))<<endl;
ans+=(lena[i]-lena[i-1])/lena[n]/lenb[m]*(
(a[i].l+a[i].r)/2*lenb[lp]-sum[lp]
+sum[m]-sum[rp-1]-(a[i].l+a[i].r)/2*(lenb[m]-lenb[rp-1])
);
for(int j=lp+1;j<rp;++j)
ans+=(lena[i]-lena[i-1])/lena[n]*(lenb[j]-lenb[j-1])/lenb[m]*cal(a[i],b[j]);
}
cout<<fixed<<setprecision(10)<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7692kb
input:
1 1 0 1 0 1
output:
0.3333333334
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7696kb
input:
1 1 0 1 1 1
output:
0.5000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7780kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.6666666269
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7708kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.0000001192
result:
ok found '1000000000.000000119', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 7704kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
-nan
result:
wrong output format Expected double, but "-nan" found