QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224804#5433. Absolute DifferenceZSH_ZSHWA 2ms12184kbC++141.6kb2023-10-23 15:06:572023-10-23 15:06:58

Judging History

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

  • [2023-10-23 15:06:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12184kb
  • [2023-10-23 15:06:57]
  • 提交

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/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: 10044kb

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

input:

1 1
0 1
1 1

output:

0.500000000015000

result:

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

Test #3:

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

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: 1ms
memory: 9972kb

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000465661

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000000

result:

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

Test #9:

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

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

result:

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

Test #10:

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

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

result:

ok found '6682.581128938', expected '6682.581127471', error '0.000000000'

Test #11:

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

input:

1000 1000
770 770
5869 5869
-8786 -8786
7549 7549
-4165 -4165
4023 4023
-9779 -9779
7797 7797
1105 1105
508 508
7653 7653
-359 -359
9393 9393
-9363 -9363
-4160 -4160
-3682 -3682
9409 9409
-8548 -8548
-9908 -9908
-7494 -7494
3751 3751
2326 2326
-3311 -3311
3651 3651
-7663 -7663
5376 5376
-7071 -7071
...

output:

6673.756817860515580

result:

ok found '6673.756817861', expected '6673.756816891', error '0.000000000'

Test #12:

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

input:

1000 1000
-735 -735
-829 -829
-6376 -6376
8558 8558
155 155
5533 5533
8800 8800
-1738 -1738
919 919
52 52
2076 2076
-6911 -6911
139 139
6733 6733
9923 9923
-4619 -4619
-9429 -9429
9902 9902
-5984 -5984
2580 2580
8738 8738
7960 7960
3388 3388
-2689 -2689
7986 7986
2565 2565
-8908 -8908
9359 9359
-434...

output:

6479.384681951301586

result:

ok found '6479.384681951', expected '6479.384680000', error '0.000000000'

Test #13:

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

input:

100 10000
82274 82408
61583 61902
-54304 -54007
-48488 -48316
-92517 -91939
85001 85160
33086 33374
36458 36573
-15785 -11838
93971 94863
50496 53064
-68609 -68302
-91873 -91176
-96937 -96753
9481 9976
83600 83691
17742 18693
55685 56039
56323 57845
88761 90277
22886 23642
30848 31047
-34662 -33470
...

output:

63142.045656425104525

result:

wrong answer 1st numbers differ - expected: '65016.2986348', found: '63142.0456564', error = '0.0288274'