QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224985#5433. Absolute DifferenceZSH_ZSHWA 1ms10180kbC++141.6kb2023-10-23 19:50:422023-10-23 19:50:43

Judging History

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

  • [2023-10-23 19:50:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10180kb
  • [2023-10-23 19:50:42]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

typedef long double db;
db eps=3e-11;

const int N=2000010;

int n,m,sa[N],sb[N],cnt;
db a[N][2],b[N][2],dis[N]; 

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin>>n>>m;
	rep(i,1,n) 
	{
		rep(j,0,1) cin>>a[i][j];
		if (fabs(a[i][0]-a[i][1])<eps) a[i][1]+=eps;
		rep(j,0,1) dis[++cnt]=a[i][j];
	}
	rep(i,1,n) 
	{
		rep(j,0,1) cin>>b[i][j];
		if (fabs(b[i][0]-b[i][1])<eps) b[i][1]+=eps;
		rep(j,0,1) dis[++cnt]=b[i][j];
	}
	sort(dis+1,dis+cnt+1);
	int sz=unique(dis+1,dis+cnt+1)-dis-1;
	
	rep(i,1,n)
	{
		int l=lower_bound(dis+1,dis+sz+1,a[i][0])-dis;
		int r=lower_bound(dis+1,dis+sz+1,a[i][1])-dis;
		sa[l]++;
		sa[r]--;
	}
	rep(i,1,m)
	{
		int l=lower_bound(dis+1,dis+sz+1,b[i][0])-dis;
		int r=lower_bound(dis+1,dis+sz+1,b[i][1])-dis;
		sb[l]++;
		sb[r]--;
	}
	rep(i,1,sz) sa[i]+=sa[i-1],sb[i]+=sb[i-1];
	
	db lena=0,lenb=0;
	rep(i,1,sz-1)
	{
		db d=dis[i+1]-dis[i];
		if (sa[i]) lena+=d;
		if (sb[i]) lenb+=d;
	}
	
	db a0=0,a1=0,b0=0,b1=0,ans=0;
	rep(i,1,sz-1)
	{
		db d=dis[i+1]-dis[i];
		db pa=d/lena,pb=d/lenb;
		db mid=(dis[i]+dis[i+1])/2;
		if (sa[i])
		{
			ans+=pa*mid*b0;
			ans-=pa*b1;
		}
		if (sb[i])
		{
			ans+=pb*mid*a0;
			ans-=pb*a1;
		}
		if (sa[i]&&sb[i])
		{
			ans+=pa*pb*d*d*d/3;
		}
		if (sa[i])
		{
			a0+=pa;
			a1+=pa*mid;
		}
		if (sb[i])
		{
			b0+=pb;
			b1+=pb*mid;
		}
	}
	
	printf("%.15Lf\n",ans); 
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10172kb

input:

1 1
0 1
0 1

output:

0.333333333333333

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 10180kb

input:

1 1
0 1
1 1

output:

0.500000000015000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

2666666666666666666756145152.000000000000000

result:

wrong answer 1st numbers differ - expected: '666666666.6666666', found: '2666666666666666518848208896.0000000', error = '4000000000000000000.0000000'