QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34427#876. Big BrotherFroggyguaAC ✓250ms58728kbC++175.6kb2022-06-08 22:22:202022-06-08 22:22:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-08 22:22:21]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:58728kb
  • [2022-06-08 22:22:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
const double PI=acos(-1.0);
//Vector可以用Point来表示 
struct Point{
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
	//相等
	friend bool operator ==(const Point &a,const Point &b){
		return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
	}
	//不相等 
	friend bool operator !=(const Point &a,const Point &b){
		return !(a==b);
	}
	//相加 
	friend Point operator + (const Point &a,const Point &b){
		return Point(a.x+b.x,a.y+b.y);
	}
	//相减 
	friend Point operator - (const Point &a,const Point &b){
		return Point(a.x-b.x,a.y-b.y);
	}
	//点积 
	friend double operator * (const Point &a,const Point &b){
		return a.x*b.x+a.y*b.y;
	}
	//叉积 
	friend double operator % (const Point &a,const Point &b){
		return a.x*b.y-a.y*b.x;
	}
	//长度 
	inline double len(){
		return sqrt(x*x+y*y);
	}
	//单位向量
	Point unit(){
		double l=len();
		return Point(x/l,y/l);
	} 
	//求单位法向量 
	inline Point normal(){
		double l=len();
		return Point(-y/l,x/l);
	}
	//点从下往上排序
	inline bool operator < (Point b){
		return fabs(y-b.y)<eps?x<b.x:y<b.y; 
	} 
	//平面直角坐标系上半部分优先
	inline bool Quad(){
		return y>eps||(fabs(y)<=eps&&x>=-eps);
	} 
};
inline Point operator * (double k,Point a){
	return Point(a.x*k,a.y*k);
}
//两个向量的夹角 
inline double Angle(Point a,Point b){
	//return acos(a*b/a.len()/b.len());
	double tmp=atan2(b.y,b.x)-atan2(a.y,a.x); 
	while(tmp>=PI+eps)tmp-=2*PI;
	while(tmp<=-PI-eps)tmp+=2*PI;
	return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
	return fabs(a%b)<=eps;
} 
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
	return b%a>eps;
} 
//逆时针旋转p后的向量 
inline Point Rotate(Point a,double p){
	return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序 

//直线 
struct Line{
	Point p[2];
	Line(Point a=Point(0,0),Point b=Point(0,0)){p[0]=a,p[1]=b;}
	inline Point& operator [] (int i){
		return p[i];
	}
	inline Point v(){
		return p[1]-p[0];
	}
};
//直线交点 
inline Point Cross(Line a,Line b){
	return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
} 
//多边形 
typedef vector<Point> Poly;
//面积 
double Area(Poly A){
	if(A.size()<=2)return 0.0;
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=A[i]%A[i+1];
	}
	tot+=A[(int)A.size()-1]%A[0];
	return fabs(tot)/2.0;
} 
//周长
double C(Poly A){
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=(A[i+1]-A[i]).len();
	}
	tot+=(A[A.size()-1]-A[0]).len();
	return tot;
} 
//重心 
Point Cent(Poly A){
	double x=0,y=0,m=0;
	for(int i=1;i<(int)A.size()-1;++i){
		double tmp=(A[i]-A[0])%(A[i+1]-A[0]);
		x+=tmp*(A[0].x+A[i].x+A[i+1].x)/3.0;
		y+=tmp*(A[0].y+A[i].y+A[i+1].y)/3.0;
		m+=tmp;
	}
	return Point(x/m,y/m);
} 
//求凸包
Poly Convex(Poly A){
	Point LTL=(*min_element(A.begin(),A.end())); //Lower Then Left
	sort(A.begin(),A.end(),[&](Point a,Point b){
		a=a-LTL,b=b-LTL;
		return Para(a,b)?a.len()<b.len():Left(b,a);
	});
	Poly st;
	for(auto p:A){
		while(st.size()>1&&!Left(p-st[(int)st.size()-2],st.back()-st[(int)st.size()-2]))st.pop_back();
		st.push_back(p);
	}
	return st;
}
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly A,Point p){
	double tot=0;
	for(int i=0;i<(int)A.size();++i)tot+=Angle(A[i]-p,A[(i+1)%A.size()]-p);
	return fabs(tot)>=eps;
} 
//多组询问
inline bool Inside_2(Poly &A,Point p){
	if(p==A[0])return true;
	if(Left(p-A[0],A[A.size()-1]-A[0])||Left(A[1]-A[0],p-A[0]))return false; 
	int pos=lower_bound(A.begin(),A.end()-1,p,[&](Point a,Point b){
		a=a-A[0],b=b-A[0];
		return Para(a,b)?a.len()<b.len():Left(b,a);
	})-A.begin();
	return !Left(A[pos]-A[pos-1],p-A[pos-1])&&A[0]<p;
}
//半平面交(HalfPlaneIntersection) <向量左侧> 
inline bool cmpang(Point a,Point b){
	return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
	return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Poly HPI(vector<Line> L){
	vector<Line> q(L.size()+10);
	static int l,r;
	sort(L.begin(),L.end());
	Poly R;
	r=1,q[l=1]=L[0];
	for(int i=1;i<(int)L.size();++i){
		if(!cmpang(q[r].v(),L[i].v()))continue;
		while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
		while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
		q[++r]=L[i];
	}
	while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
	while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
	q[r+1]=q[l];
	for(int i=l;i<=r;++i){
		R.push_back(Cross(q[i],q[i+1]));
	}
	return R;
}

//Minkowski
inline Poly operator + (const Poly &A,const Point &p){
	Poly C=A;
	for(auto &t:C)t=t+p;
	return C;
}
inline Poly operator + (const Poly &A,const Poly &B){
	if(A.empty())return B;
	if(B.empty())return A;
	if(A.size()==1)return B+A[0];
	if(B.size()==1)return A+B[0];
	Poly R;
	int i=0,j=0;
	R.push_back(A[0]+B[0]);
	while(true){
		Point vA=A[(i+1)%A.size()]-A[i],vB=B[(j+1)%B.size()]-B[j];
		if(Para(vA,vB)?vA.Quad()==vB.Quad():Left(vA,vB)){
			i=(i+1)%A.size();
		}
		else{
			j=(j+1)%B.size();
		}
		R.push_back(A[i]+B[j]);
		if(!i&&!j)break; 
	}
	R.pop_back();
	return R;
}
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);
	vector<Line> L;
	cin>>n;
	Poly A(n);
	for(int i=0;i<n;++i){
		cin>>A[i].x>>A[i].y;
	}
	for(int i=0;i<n;++i){
		L.emplace_back(A[(i+1)%n],A[i]);
	}
	cout<<Area(HPI(L))<<'\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3736kb

input:

8
0 0
0 1
1 1
1 2
2 2
2 1
3 1
3 0

output:

1.0000000000

result:

ok "1.000000000"

Test #2:

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

input:

8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0

output:

0.0000000000

result:

ok "0.000000000"

Test #3:

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

input:

6
140 62
97 141
68 156
129 145
153 176
130 109

output:

48.8034950021

result:

ok "48.803495002"

Test #4:

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

input:

3
198 165
322 122
242 84

output:

4076.0000000000

result:

ok "4076.000000000"

Test #5:

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

input:

15
0 250
30 250
125 250
180 250
250 250
250 100
250 80
250 0
140 0
100 0
73 0
0 0
0 2
0 30
0 90

output:

62500.0000000000

result:

ok "62500.000000000"

Test #6:

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

input:

16
146 145
109 229
139 301
164 385
221 433
309 419
405 420
447 369
501 308
498 229
471 150
456 75
391 39
308 47
227 39
166 73

output:

114711.3646559959

result:

ok "114711.364655996"

Test #7:

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

input:

6
160 210
200 210
200 300
280 300
200 170
200 80

output:

0.0000000000

result:

ok "0.000000000"

Test #8:

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

input:

8
198 165
230 113
246 117
281 161
266 36
247 68
228 79
200 30

output:

63.7023612504

result:

ok "63.702361250"

Test #9:

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

input:

14
198 165
274 226
258 318
297 348
339 309
372 360
336 265
347 203
388 161
346 123
306 155
293 87
261 112
242 84

output:

2189.0016479133

result:

ok "2189.001647913"

Test #10:

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

input:

150
9956003 4338159
9912302 4099714
9868603 3861269
9803272 3631902
9737943 3402535
9725452 3366405
9712963 3330276
9696862 3286153
9680763 3242031
9604920 3061837
9529080 2881643
9480997 2784399
9432916 2687155
9193856 2313907
8954799 1940659
8617533 1583544
8280269 1226429
8207226 1165339
8134185 ...

output:

77922149990018.1250000000

result:

ok "77922149990018.218750000"

Test #11:

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

input:

1000
9999605 4937170
9999012 4905760
9998421 4874350
9997433 4842949
9996447 4811549
9995065 4780163
9993685 4748778
9991908 4717412
9990134 4686047
9987963 4654706
9985795 4623366
9983230 4592055
9980668 4560744
9977710 4529467
9974755 4498191
9971405 4466954
9968057 4435718
9964314 4404526
9960574...

output:

78537708558542.0781250000

result:

ok "78537708558542.031250000"

Test #12:

score: 0
Accepted
time: 28ms
memory: 8952kb

input:

50000
10000000 4998743
9999998 4998115
9999999 4997487
9999998 4996858
9999999 4996230
9999997 4995601
9999997 4994973
9999995 4994345
9999996 4993717
9999994 4993088
9999994 4992460
9999992 4991832
9999992 4991204
9999990 4990575
9999990 4989947
9999987 4989318
9999987 4988690
9999984 4988062
99999...

output:

78539327974559.6093750000

result:

ok "78539327974559.937500000"

Test #13:

score: 0
Accepted
time: 130ms
memory: 30924kb

input:

250000
10000000 4999749
9999999 4999623
10000000 4999497
9999999 4999371
10000000 4999246
9999999 4999120
10000000 4998995
9999999 4998869
10000000 4998743
9999999 4998617
10000000 4998492
9999999 4998366
10000000 4998241
9999999 4998115
10000000 4997989
9999998 4997863
9999999 4997738
9999998 49976...

output:

78525334096415.2343750000

result:

ok "78525334096415.250000000"

Test #14:

score: 0
Accepted
time: 243ms
memory: 58224kb

input:

500000
10000000 4999874
9999999 4999811
10000000 4999749
9999999 4999686
10000000 4999623
9999999 4999560
10000000 4999497
9999999 4999434
10000000 4999372
9999999 4999309
10000000 4999246
9999999 4999183
10000000 4999120
9999999 4999057
10000000 4998995
9999999 4998932
10000000 4998869
9999999 4998...

output:

78479009888752.8593750000

result:

ok "78479009888752.796875000"

Test #15:

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

input:

150
9725000 5000000
9496052 4811560
9932639 4585795
9464516 4436001
9658831 4212018
9401664 4064398
9794486 3768986
9307937 3699357
9462178 3446106
9183994 3343440
9522050 2986654
9030702 2999142
9140549 2723714
8849139 2668879
9122960 2260712
8640576 2354967
8702951 2065077
8406477 2059608
8608394 ...

output:

11331974361764.5527343750

result:

ok "11331974361764.560546875"

Test #16:

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

input:

1000
9725000 5000000
9499911 4971726
9949609 4937799
9499200 4915183
9723507 4881261
9497779 4858652
9946482 4813434
9495648 4802144
9719032 4762596
9492806 4745667
9940232 4689187
9489256 4689230
9711575 4644081
9484996 4632843
9930861 4565137
9480028 4576513
9701143 4525791
9474353 4520250
9918375...

output:

302585512646.1289062500

result:

ok "302585512646.140625000"

Test #17:

score: 0
Accepted
time: 24ms
memory: 8800kb

input:

50000
9725000 5000000
9499999 4999435
9949999 4998756
9499999 4998304
9724999 4997625
9499999 4997173
9949998 4996268
9499998 4996042
9724997 4995250
9499997 4994911
9949996 4993780
9499995 4993780
9724994 4992875
9499993 4992649
9949992 4991292
9499992 4991518
9724990 4990500
9499989 4990387
994998...

output:

121175133.1425781250

result:

ok "121175133.132812500"

Test #18:

score: 0
Accepted
time: 114ms
memory: 30908kb

input:

250000
9725000 5000000
9499999 4999887
9949999 4999752
9499999 4999661
9724999 4999525
9499999 4999435
9949999 4999254
9499999 4999209
9724999 4999050
9499999 4998983
9949999 4998756
9499999 4998756
9724999 4998575
9499999 4998530
9949999 4998259
9499999 4998304
9724999 4998100
9499999 4998078
99499...

output:

4772368.0546875000

result:

ok "4772368.076171875"

Test #19:

score: 0
Accepted
time: 242ms
memory: 58692kb

input:

500000
9725000 5000000
9499999 4999944
9949999 4999876
9499999 4999831
9724999 4999763
9499999 4999718
9949999 4999627
9499999 4999605
9724999 4999525
9499999 4999492
9949999 4999378
9499999 4999378
9724999 4999288
9499999 4999265
9949999 4999130
9499999 4999152
9724999 4999050
9499999 4999039
99499...

output:

1169025.6074218750

result:

ok "1169025.593750000"

Test #20:

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

input:

72
4 50
4 51
5 56
6 60
7 63
9 68
10 70
13 75
15 78
18 82
19 83
23 86
26 88
31 91
33 92
38 94
41 95
45 96
50 97
51 97
56 96
60 95
63 94
68 92
70 91
75 88
78 86
82 83
83 82
86 78
88 75
91 70
92 68
94 63
95 60
96 56
97 51
97 50
96 45
95 41
94 38
92 33
91 31
88 26
86 23
83 19
82 18
78 15
75 13
70 10
68 ...

output:

6435.0000000000

result:

ok "6435.000000000"

Test #21:

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

input:

72
4 50
4 51
5 56
6 60
7 63
9 68
10 70
13 75
15 78
18 82
20 82
23 86
26 88
31 91
33 92
38 94
41 95
45 96
50 97
51 97
56 96
60 95
63 94
68 92
70 91
75 88
78 86
82 83
83 82
86 78
88 75
91 70
91 68
94 63
95 60
96 56
97 51
97 50
96 45
95 41
94 38
92 33
91 31
88 26
86 23
83 19
82 18
78 15
75 13
70 10
68 ...

output:

4180.1000000000

result:

ok "4180.100000000"

Test #22:

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

input:

336
10 500
10 501
11 512
12 522
13 531
14 539
15 546
16 552
18 563
19 568
21 577
22 581
25 592
27 599
30 609
31 612
35 623
38 631
40 636
43 643
47 652
52 663
53 665
59 676
64 685
68 692
71 697
76 705
83 716
85 719
92 729
97 736
105 747
108 751
115 760
119 765
128 776
133 782
139 789
146 797
154 806
...

output:

708179.0000000000

result:

ok "708179.000000000"

Test #23:

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

input:

336
10 500
10 501
11 512
12 522
13 531
14 539
15 546
16 552
18 563
19 568
21 577
22 581
25 592
27 599
30 609
31 612
35 623
38 631
40 636
43 643
47 652
52 663
53 665
59 676
64 685
68 692
71 697
76 705
83 716
85 719
92 729
97 736
105 747
109 750
115 760
119 765
128 776
133 782
139 789
146 797
154 806
...

output:

696280.0758658010

result:

ok "696280.075865801"

Test #24:

score: 0
Accepted
time: 3ms
memory: 3876kb

input:

1576
22 5000
22 5001
23 5026
24 5050
25 5073
26 5095
27 5116
28 5136
29 5155
30 5173
31 5190
32 5206
33 5221
34 5235
35 5248
37 5273
38 5285
40 5308
41 5319
43 5340
44 5350
46 5369
47 5378
49 5395
52 5420
53 5428
56 5451
58 5466
61 5488
62 5495
65 5515
67 5528
70 5547
74 5572
75 5578
79 5601
82 5618...

output:

73741747.0000000000

result:

ok "73741747.000000000"

Test #25:

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

input:

1576
22 5000
22 5001
23 5026
24 5050
25 5073
26 5095
27 5116
28 5136
29 5155
30 5173
31 5190
32 5206
33 5221
34 5235
35 5248
37 5273
38 5285
40 5308
41 5319
43 5340
44 5350
46 5369
47 5378
49 5395
52 5420
53 5428
56 5451
58 5466
61 5488
62 5495
65 5515
67 5528
70 5547
74 5572
75 5578
79 5601
82 5618...

output:

73705049.0762995631

result:

ok "73705049.076299563"

Test #26:

score: 0
Accepted
time: 4ms
memory: 4376kb

input:

7328
7 50000
7 50001
8 50056
9 50110
10 50163
11 50215
12 50266
13 50316
14 50365
15 50413
16 50460
17 50506
18 50551
19 50595
20 50638
21 50680
22 50721
23 50761
24 50800
25 50838
26 50875
27 50911
28 50946
29 50980
30 51013
31 51045
32 51076
33 51106
34 51135
35 51163
37 51218
38 51245
40 51298
41...

output:

7448951491.0000000000

result:

ok "7448951491.000000000"

Test #27:

score: 0
Accepted
time: 4ms
memory: 4308kb

input:

7328
7 50000
7 50001
8 50056
9 50110
10 50163
11 50215
12 50266
13 50316
14 50365
15 50413
16 50460
17 50506
18 50551
19 50595
20 50638
21 50680
22 50721
23 50761
24 50800
25 50838
26 50875
27 50911
28 50946
29 50980
30 51013
31 51045
32 51076
33 51106
34 51135
35 51163
37 51218
38 51245
40 51298
41...

output:

7448332528.5340909958

result:

ok "7448332528.534090042"

Test #28:

score: 0
Accepted
time: 18ms
memory: 8552kb

input:

33920
55 500000
55 500001
56 500119
57 500236
58 500352
59 500467
60 500581
61 500694
62 500806
63 500917
64 501027
65 501136
66 501244
67 501351
68 501457
69 501562
70 501666
71 501769
72 501871
73 501972
74 502072
75 502171
76 502269
77 502366
78 502462
79 502557
80 502651
81 502744
82 502836
83 5...

output:

741575176515.0000000000

result:

ok "741575176515.000000000"

Test #29:

score: 0
Accepted
time: 25ms
memory: 8432kb

input:

33920
55 500000
55 500001
56 500119
57 500236
58 500352
59 500467
60 500581
61 500694
62 500806
63 500917
64 501027
65 501136
66 501244
67 501351
68 501457
69 501562
70 501666
71 501769
72 501871
73 501972
74 502072
75 502171
76 502269
77 502366
78 502462
79 502557
80 502651
81 502744
82 502836
83 5...

output:

741573412548.7573242188

result:

ok "741573412548.757324219"

Test #30:

score: 0
Accepted
time: 96ms
memory: 30272kb

input:

157336
187 5000000
187 5000001
188 5000256
189 5000510
190 5000763
191 5001015
192 5001266
193 5001516
194 5001765
195 5002013
196 5002260
197 5002506
198 5002751
199 5002995
200 5003238
201 5003480
202 5003721
203 5003961
204 5004200
205 5004438
206 5004675
207 5004911
208 5005146
209 5005380
210 5...

output:

74106620545235.0000000000

result:

ok "74106620545235.000000000"

Test #31:

score: 0
Accepted
time: 96ms
memory: 27540kb

input:

157336
187 5000000
187 5000001
188 5000256
189 5000510
190 5000763
191 5001015
192 5001266
193 5001516
194 5001765
195 5002013
196 5002260
197 5002506
198 5002751
199 5002995
200 5003238
201 5003480
202 5003721
203 5003961
204 5004200
205 5004438
206 5004675
207 5004911
208 5005146
209 5005380
210 5...

output:

74103087971323.8750000000

result:

ok "74103087971323.890625000"

Test #32:

score: 0
Accepted
time: 3ms
memory: 4024kb

input:

1000
2600927 1831555
2984114 2324333
2787576 1961497
2689538 1755826
3028761 2094323
3008306 1946570
2887360 1607548
2631170 1248827
2470347 1030200
2599775 976740
2355502 478504
3115957 1757729
3013991 1652055
3820728 3275946
3463130 2975465
2475784 1734142
1806440 809618
1228787 158466
889070 1047...

output:

0.0000000000

result:

ok "0.000000000"

Test #33:

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

input:

100
3929758 5668516
3749933 7186400
3671700 7927629
3735926 8648648
3696539 9488835
4063262 5499567
4098011 5704292
4139678 6088717
4070777 5280029
4228917 6549215
4520598 8419214
4828480 8246428
4211962 5750987
4483103 6401689
4610886 6564084
5813897 9050031
5230681 7607146
6109094 7997896
5521186 ...

output:

4397951.3378906250

result:

ok "4397951.332031250"

Test #34:

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

input:

339
9841560 4381918
5523440 4169860
9115892 4287496
8727198 4244767
5647505 4166184
6094829 4167703
8084370 4141154
8447161 4040556
7127522 4080692
9371627 3948065
8433750 3853008
8813865 3806327
5596744 4123253
9468765 3650496
8552072 3729494
7603308 3772657
9093114 3424080
6269139 3962293
5674235 ...

output:

32849.0781250000

result:

ok "32849.078125000"

Test #35:

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

input:

4063
499799 2678043
2533563 4266964
403464 2618451
1221250 3278868
105760 2429242
226632 2525041
215412 2517220
64334 2404256
2592208 4345606
811663 3027094
4044746 5463601
1404325 3485231
1786865 3771953
1076645 3252401
99034 2529000
3694400 5206336
2511697 4333861
73213 2556268
2066557 4031607
138...

output:

232.3027343750

result:

ok "232.306640625"

Test #36:

score: 0
Accepted
time: 15ms
memory: 5700kb

input:

20000
8066872 8602921
8232035 8787201
5776793 6015019
5878121 6129006
5025917 5167705
8660957 9266687
8658850 9263857
5327441 5507461
6546784 6882138
9179876 9850214
6853075 7226685
8949733 9588511
6930959 7311116
7507630 7960229
6399255 6711831
9080160 9728973
7405711 7844429
6878616 7249568
747610...

output:

0.0742187500

result:

ok "0.074218750"

Test #37:

score: 0
Accepted
time: 250ms
memory: 58728kb

input:

500000
953759 7297457
2580377 6153306
2634043 6115587
2839957 5970786
486723 7626180
2227022 6402004
1225883 7106390
139747 7870702
404456 7684670
1928896 6612075
549400 7583058
1773913 6721479
425016 7670854
2329665 6330471
465562 7642533
375055 7706403
601385 7547144
198343 7830881
359197 7717867
...

output:

0.0000000000

result:

ok "0.000000000"

Test #38:

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

input:

1000
1775807 6865631
4871886 8023283
7398086 8967646
143850 6312725
50868 6279999
4241424 7822696
22120 6286274
1098695 6682176
2064750 7034586
1875528 6981944
2387779 7184399
4969521 8131866
3585627 7642928
1961372 7069219
4352603 7948808
6407440 8673598
1789021 7127821
2036724 7247311
2738127 7483...

output:

5130.8359375000

result:

ok "5130.828125000"

Test #39:

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

input:

997
6923752 3142103
6035265 1166112
7134771 3679045
6503138 2357309
5554003 296869
6328294 2053182
5780625 885548
7317116 4249183
7819975 5401363
5642829 856378
7197673 4155115
7364650 4528812
6776562 3318236
5364427 497625
8844837 7590432
6698006 3244990
7640716 5174617
8857860 7626107
6979782 3911...

output:

5131.8281250000

result:

ok "5131.828125000"

Test #40:

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

input:

1000
9150738 1660620
8900040 3385771
9165624 1099746
9250879 361608
9026045 2195006
9016856 2243604
8908088 3047880
8641345 5262477
8796554 3843222
8898993 2719422
9033383 1282868
9110500 514669
8853009 2956351
9100138 459660
8690975 4209259
9048387 560131
8975462 1191225
8601171 5002153
8675233 419...

output:

29111.7734375000

result:

ok "29111.765625000"