QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224724#5433. Absolute DifferenceZSH_ZSH#WA 1ms10176kbC++141.5kb2023-10-23 11:20:102023-10-23 11:20:11

Judging History

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

  • [2023-10-23 11:20:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10176kb
  • [2023-10-23 11:20:10]
  • 提交

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=1e-15;

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];
		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];
		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/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: 0ms
memory: 10048kb

input:

1 1
0 1
0 1

output:

0.333333333333334

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686069

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000000

result:

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

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 10176kb

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

0.000000000000000

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'