QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150619#5433. Absolute DifferencetanaoWA 2ms7780kbC++141.7kb2023-08-25 21:59:072023-08-25 21:59:09

Judging History

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

  • [2023-08-25 21:59:09]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7780kb
  • [2023-08-25 21:59:07]
  • 提交

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;
}

详细

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