QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110028#5570. Epidemic Escape2024zllAC ✓488ms7928kbC++143.4kb2023-05-31 10:26:062023-05-31 10:26:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 10:26:26]
  • 评测
  • 测评结果:AC
  • 用时:488ms
  • 内存:7928kb
  • [2023-05-31 10:26:06]
  • 提交

answer

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	char input[ARR_SIZE],*si=input,*ti=input;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=num*10+(ch^48),ch=gc();
		flag||(num=-num);
	}
}
using IO::read;
typedef double real;
const int maxn=100000,maxk=5;
const real eps=1e-16;
int n,q;
struct Vector{
	real x,y;
	Vector(const real x=0,const real y=0):x(x),y(y){}
	friend bool operator<(const Vector&A,const Vector&B){
		return A.x!=B.x?A.x<B.x:A.y<B.y; 
	}
	friend Vector operator-(const Vector&A,const Vector&B){
		return Vector(A.x-B.x,A.y-B.y);
	}
	friend Vector operator/(const Vector&A,const real&x){
		return Vector(A.x/x,A.y/x);
	}
	friend real Cross(const Vector&A,const Vector&B){
		return A.x*B.y-A.y*B.x;
	}
	friend real Dot(const Vector&A,const Vector&B){
		return A.x*B.x+A.y*B.y;
	}
	Vector rotate_90(){
		return Vector(-y,x);
	}
}P[maxn],Q;
bool used[maxn];
std::vector<int>down[maxk],up[maxk],stack;
void PolygonToConvex(std::vector<int>&down,std::vector<int>&up,std::vector<int>&stack){
	int end=n-1;
	while(end>=0&&used[end])end--;
	if(end==-1)return;
	stack.resize(n*2);
	int top=-1;
	for(int i=0;i<=end;i++){
		if(used[i])continue;
		while(top>0&&Cross(P[stack[top]]-P[stack[top-1]],P[i]-P[stack[top]])<=0)top--;
		stack[++top]=i;
	}
	const int k=top;
	for(int i=end-1;i>=0;i--){
		if(used[i])continue;
		while(top>k&&Cross(P[stack[top]]-P[stack[top-1]],P[i]-P[stack[top]])<=0)top--;
		stack[++top]=i;
	}
	stack.resize(top+1);
	for(int i:stack)used[i]=true;
	down.assign(stack.begin(),stack.begin()+k+1);
	if(k<top)up.assign(stack.begin()+k+1,stack.begin()+top+1);
}
int k;
real DotPQ[maxn];
struct CMP{
	bool operator()(const int x,const int y)const{
		return DotPQ[x]>DotPQ[y];
	}
}cmp;
std::priority_queue<int,std::vector<int>,CMP>queue;
int vis[maxn],now_id;
void push(const int x){
	if(vis[x]==now_id)return;
	vis[x]=now_id;
	if((DotPQ[x]=Dot(P[x],Q))<=eps)return;
	queue.push(x);
	if((int)queue.size()>k)queue.pop();
}
void solve(std::vector<int>&vec,const bool flag){
	if((int)vec.size()<=k)
		for(int i:vec)
			push(i);
	else{
		for(int i=0;i<k;i++)push(vec[i]);
		for(int i=(int)vec.size()-k;i<(int)vec.size();i++)push(vec[i]);
		int l=0,r=(int)vec.size()-2,mid;
		if(flag)
			while(l<r){
				mid=(l+r)>>1;
				if(Dot(Q,P[vec[mid+1]]-P[vec[mid]])<0)r=mid;
				else l=mid+1;
			}
		for(int i=std::max(0,l-k),lim=std::min((int)vec.size()-1,l+k);i<=lim;i++)push(vec[i]);
	}
}
int main(){
	read(n);
	for(int i=0;i<n;i++)read(P[i].x),read(P[i].y),P[i]=P[i]/Dot(P[i],P[i]);
	std::sort(P,P+n);
	for(int i=0;i<maxk;i++)PolygonToConvex(down[i],up[i],stack);
	read(q);
	memset(vis,-1,sizeof(int)*n);
	for(int i=0,x,y;i<q;i++){
		now_id=i;
		read(x),read(y),read(k);
		if(x==0&&y==0){
			puts("-1");
			continue;
		}
		Q=Vector(x,y);
		Q=Q/sqrt(Dot(Q,Q));
		while(!queue.empty())queue.pop();
		for(int j=0;j<k;j++)solve(down[j],y<0);
		for(int j=0;j<k;j++)solve(up[j],y>0);
		if((int)queue.size()<k)puts("-1");
		else printf("%.7lf\n",(real)0.5/Dot(P[queue.top()],Q));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1

output:

8.7002554
3.2260196

result:

ok 2 numbers

Test #2:

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

input:

8
4 -1
4 -8
0 9
4 -7
-5 -2
5 -5
7 5
-9 2
10
4 -8 1
7 -7 5
-10 8 2
-9 9 2
4 -7 5
-1 -10 2
6 -3 2
2 -9 3
-10 -10 1
5 9 1

output:

3.1677630
26.1629509
5.4614883
6.3639610
-1
5.2894082
3.7267800
4.6097722
2.9294424
4.7617289

result:

ok 10 numbers

Test #3:

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

input:

5
-4 -7
5 0
2 4
-7 -7
4 4
20
0 -5 2
-4 -7 2
-7 7 3
4 -4 3
-7 4 3
4 -4 1
2 4 1
6 -7 2
4 -4 2
4 4 3
5 4 1
-1 9 2
8 9 3
4 -4 2
6 3 3
-10 -3 2
-7 7 1
9 -4 1
-4 -7 3
-2 0 2

output:

7.0000000
5.1305277
-1
-1
-1
3.5355339
2.2360680
11.9854078
15.3206469
3.5355339
2.4627401
4.5276926
3.7629983
15.3206469
2.9814240
5.6217035
7.0710678
2.7357938
-1
8.1250000

result:

ok 20 numbers

Test #4:

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

input:

100
63 -48
20 -62
-81 -31
-17 -93
2 -74
72 25
-71 37
-71 17
56 67
-47 65
-89 14
62 30
-71 -33
14 -53
-57 -52
30 80
-14 -69
-45 -19
-54 -71
58 -20
-57 12
5 -56
-76 -2
26 61
24 60
10 -97
-63 38
17 81
-43 -38
44 35
-86 37
62 72
77 11
41 29
14 81
77 55
-54 -33
-43 -51
76 14
55 47
43 24
69 -13
16 75
11 9...

output:

26.7586789
29.5714060
24.6221445
27.7717457
26.6783667
24.4237025
28.8933482
29.7761696
31.9403630
27.2149016
31.7280950
27.0711606
25.2991100
26.8710652
28.9958395
28.3563142
29.9872589
25.6496237
25.1496681
28.3011570
28.6117520
26.6901575
28.3504852
30.8282427
29.3782484
26.3805222
30.6454143
29....

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 9ms
memory: 5304kb

input:

10000
-3 3
-6 2
-4 1
-2 -5
5 -6
-7 -2
0 7
1 -4
8 0
-4 4
-6 -2
5 0
2 9
-4 -8
0 -8
7 4
-7 2
3 3
4 1
-1 7
-4 -2
6 0
3 -5
-7 2
0 -9
7 0
7 3
-6 0
1 7
6 2
2 -9
1 8
3 -3
2 -9
4 2
4 -5
6 0
-3 6
7 3
0 8
0 -4
7 0
-5 8
5 -5
-5 -1
0 9
-4 -3
-9 -1
7 -2
-7 -2
4 0
-6 6
-3 4
6 7
2 5
-8 -5
0 5
4 0
0 -4
0 -6
-5 3
-5 ...

output:

2.1549170
2.1672659
2.0676431
2.1118420
2.1118420
2.1118420
2.1249873
2.1213203
2.0275875
2.0928823
2.1415372
2.0615528
2.1549170
2.0000000
2.1213203
2.1672659
2.0676431
2.0203051
2.0676431
2.1415372
2.1213203
2.0000000
2.1213203
2.0626978
2.1213203
2.1118420
2.0615528
2.0000000
2.1633308
2.0203051
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 16ms
memory: 6044kb

input:

10000
-90174 318421
-37261 138897
-260388 -302590
-906833 35071
317743 -283220
390311 -85301
880987 325969
-315218 -116767
103089 -8223
-134988 -973121
-444593 229407
-552060 549321
265624 -337609
-264546 322379
28687 110143
467764 303005
-335748 32188
213125 274156
240105 751
-81255 -129323
148563 ...

output:

218.3023759
481.6627120
792.1850756
579.9542618
807.7094463
242.5921755
882.2675148
530.7807803
664.1821760
796.3607398
662.7071679
639.0726193
125.8211827
745.7291753
732.4967218
676.5327801
808.9964119
427.9627408
1298.3736892
616.3789303
854.0497083
391.9218250
993.4890020
796.2978716
609.8549642...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 104ms
memory: 6660kb

input:

100000
-14593321 17388753
13488647 1223793
33907737 -8731155
-14502324 73522129
-13933178 -13752140
9462275 13349398
14636622 31405249
5160247 -69775840
-49415260 -40092130
-9926862 -25806124
14982829 -8025116
-5492901 4568113
48872077 86636033
19374632 32538501
-16657133 -11624530
-15398598 -966935...

output:

1331.4977763
1193.9602287
1171.2427262
1856.2890363
2681.8829459
1170.8707408
1128.3614716
1855.8783380
3518.3241480
1541.7860082
1515.0151223
1124.4065660
2146.7167113
1179.4306789
1164.1588783
1251.5110829
2737.3506509
1117.3515870
2213.1263919
1434.5146831
1378.5510007
1753.1862620
1180.4099743
1...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 150ms
memory: 7788kb

input:

100000
-60674143 79489917
99210432 12541486
-99948887 -3196593
57015830 -82153478
10407645 99456921
-90320128 42921703
93983821 34161956
96773928 -25195355
69603194 71801068
27259746 -96212811
96031961 27890165
76618755 -64261689
-99095784 13417302
-95521354 -29591717
-34815155 -93743823
-93393132 -...

output:

49999995.0818662
49999995.9004091
49999995.3149217
49999995.3054674
49999994.5577050
49999996.4862814
49999994.6940732
49999995.1368904
49999995.7255438
49999995.4937631
49999997.2567733
49999994.7944018
49999994.9287077
49999995.7829387
49999994.9440986
49999995.0367875
49999995.0913404
49999995.12...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 165ms
memory: 7720kb

input:

100000
28442101 95869943
64560849 76366848
-85662377 51594149
95580169 -29401185
-40181553 -91572058
67627360 -73665047
82527643 56472888
29700208 95487675
87983116 -47528622
62992785 77665358
-2222699 99975284
-64132427 76726992
-76047272 64936977
87016456 49276108
95274227 30377974
-62944509 -7770...

output:

49999994.8309710
49999995.5183789
49999994.9251787
49999995.5234947
49999994.8275525
49999994.6394858
49999994.8678172
49999996.4713343
49999995.0233867
49999995.4033335
49999994.9916431
49999994.9030464
49999995.6710114
49999995.2659545
49999995.3312549
49999995.1957079
49999996.5504021
49999996.11...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 148ms
memory: 7464kb

input:

100000
66926611 74302272
-39804607 -91736532
-31850108 94792239
-94396583 -33004302
-57766222 81627580
-80246004 59670576
74979879 -66166588
37426246 -92732280
-40775354 -91309200
99674197 8065507
94244794 -33435279
-24613128 -96923641
28694420 -95794726
97637671 -21607478
-49066338 -87134919
612455...

output:

49999995.7715908
49999995.4357772
49999996.4043742
49999994.8179789
49999997.2285060
49999995.8582851
49999995.0825320
49999994.5402302
49999994.6179781
49999995.4909426
49999995.5851057
49999994.7581311
49999997.0426210
49999994.9688381
49999995.9953611
49999994.5732258
49999995.2128755
49999994.88...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 170ms
memory: 7664kb

input:

100000
31516589 94903656
70239724 71178504
-57719682 81660501
73612201 67684871
82391354 -56671542
72801723 -68555878
26893692 -96315770
-83483265 55050367
87478845 -48450493
-85026739 52635096
-26511823 96421583
95776532 -28755096
88242174 -47045913
77725402 -62918677
-14344932 98965762
-25054341 -...

output:

49999995.1416610
49999995.1742069
49999995.8579723
49999997.1304232
49999995.6565238
49999995.2441421
49999995.3516391
49999994.6824237
49999995.6391572
49999995.6166996
49999995.0758055
49999997.0231123
49999994.7090392
49999996.2098523
49999995.4048886
49999995.6618597
49999995.3567084
49999996.34...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 164ms
memory: 7456kb

input:

100000
-77953946 -62635297
-97003745 24295529
-95559516 -29468254
-37774475 -92590972
-78235761 62282941
24449261 96965108
-32126090 -94699061
-90361637 -42834246
-15234257 -98832767
-67393723 -73878858
-77089954 63695658
-87433336 -48532575
45142341 -89230981
80543145 -59268883
99006350 -14062036
-...

output:

49999994.8800610
49999995.6036443
49999995.4473164
49999994.8234286
49999994.7814366
49999994.9757975
49999994.9918332
49999996.4288837
49999995.4920812
49999996.1784077
49999995.1575361
49999994.5227593
49999995.0962232
49999994.7197688
49999995.0631763
49999994.7060053
49999995.7511571
49999995.73...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 131ms
memory: 7120kb

input:

100000
-14994761 -98790003
-52791662 84821895
87513045 48313812
19785427 97922747
98912337 -14130131
-4520530 -99837938
93690283 34834919
99547007 8570663
86380533 -50241768
-46722739 88350371
69496929 -71791216
-85910197 -51161960
5199588 99844597
11410781 -99298438
-99814172 5122831
99748209 57815...

output:

49950309.3056238
49950587.9321184
49950271.2551975
49950284.2250954
49950441.6709376
49950141.2846822
49950288.3766497
49950469.2183908
49950744.1464029
49950688.2312026
49950339.5676554
49950216.2988869
49950092.5740196
49950416.5313250
49950177.6632704
49950096.3856720
49950451.9614393
49950429.24...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 316ms
memory: 7472kb

input:

100000
87107311 49115334
-98093001 -19436093
86159431 -50759733
-90576186 -42378693
99725385 7405849
-93030414 -36678893
7164898 99742981
88908273 -45774642
-87848897 47776244
98650729 -16371688
-13992770 99016167
-36675953 93031566
-28482368 95857989
-38312130 -92369793
86372731 50395931
-50997291 ...

output:

49999995.7797225
49999994.6245876
49999998.3509638
49999995.5115784
49999995.0933499
49999994.8836178
49999997.9886450
49999996.2295946
49999998.0441680
49999995.8618393
49999996.7392814
49999996.2061849
49999996.8127210
49999997.1296632
49999998.4672184
49999995.6843000
49999995.6223850
49999996.47...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 308ms
memory: 7784kb

input:

100000
87353211 -48676647
78574311 -61855286
1089525 99994063
-99999914 -125343
-79940915 -60078697
97608574 -21738565
-99570798 9254977
-57082835 -82106930
77989099 62591525
-36640991 -93045345
-82795 -99999957
99857762 5331654
91364668 40650900
-89488349 -44629962
24733984 96892872
87543386 483337...

output:

49999998.4114885
49999997.9731765
49999997.2725407
49999998.4609082
49999994.7726249
49999996.2591437
49999997.4391602
49999997.4595153
49999994.9463550
49999996.9207553
49999997.9735086
49999996.5709999
49999996.1017815
49999997.6848153
49999995.7377748
49999997.1418929
49999995.7563544
49999996.50...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 293ms
memory: 7352kb

input:

100000
-95807142 28504127
58593535 -80943524
-99766431 5986168
93220087 -35989826
3645498 -99841657
69856363 -71476864
6430623 99747801
99074166 -13444307
25226151 96750874
-99820804 -4584947
80958147 58644185
99854141 3972407
93127038 36267563
83656508 -54710699
73943321 -67286687
22540877 -9736065...

output:

49951675.8764738
49951660.7759727
49951740.4114056
49951465.4638304
49950200.2577471
49950954.5130790
49951162.3204078
49950823.9987230
49951011.4364624
49951169.7614417
49950251.9870869
49950960.8967498
49951548.7213695
49950976.9117757
49950703.5493175
49950605.7424022
49950450.2345912
49951138.30...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 294ms
memory: 7400kb

input:

100000
-18866705 98167110
96374803 -26445175
-90527905 42406852
93525949 35171769
-99675297 7020406
-99946706 -2220134
31631621 -94776631
-46384811 88576816
-2476324 99950315
69306249 -72003171
-30910251 -95067123
85457008 51882654
82372940 -56613508
6032490 99757677
99488049 -9473775
97295326 22667...

output:

49950435.4342463
49950523.6429178
49951727.0368674
49950791.7197092
49952062.1846698
49951220.3037158
49950723.9434544
49951030.2751690
49951362.7755594
49951028.0508876
49951744.1141123
49951224.7437645
49952317.4008080
49951224.1601772
49951151.4789893
49951586.3310275
49950846.4368763
49950386.43...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 325ms
memory: 7360kb

input:

100000
-94544376 30244008
-5524553 -99134196
64736465 74935295
-10781223 -98537615
-27540414 96110283
94534101 -30554453
-49000527 -87040163
-70553197 70503800
90093758 -41264733
51497088 84792240
-50688507 -85177162
95747827 28411115
-85773541 -50275968
-34190721 93830767
-42611828 90282250
-315970...

output:

49503286.6071342
49503940.1660004
49500902.0574531
49502328.8001763
49504050.8899426
49503864.7113224
49502762.9502232
49505338.4543824
49503140.1828940
49508220.5136476
49506314.7348971
49508005.3967641
49501854.4901582
49506908.0257155
49503251.9579029
49506725.8744599
49500729.9641182
49510344.37...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 259ms
memory: 7396kb

input:

100000
-72724429 68353169
-23398454 96972722
98697156 15295066
-50053634 86257978
95660227 -25689933
-98427638 12257835
-95720479 25986032
99360720 -9958797
-34453585 -93167496
97657115 21470158
-61854668 77939046
-78666489 60608092
99656422 -4271277
37176490 92108858
92266107 -36908241
84966021 -52...

output:

49505232.2522462
49505902.9530284
49506391.3517989
49501384.8619998
49501974.5375368
49503956.2921275
49506260.8484405
49507848.9578431
49507844.1977250
49507646.9159879
49505334.2111403
49504283.4305713
49503897.6784183
49506239.9631957
49506420.6701119
49504569.2480966
49504075.6490348
49504751.43...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 265ms
memory: 7252kb

input:

100000
-98189095 15784434
89982407 42479712
-98538151 10378719
48446566 -87123427
90936804 -40512021
67828507 72315413
-19102654 97627943
-40632682 -90422395
-71928032 68028353
59463681 -80194272
-61979681 77927882
-89859188 -41650204
-40753972 -90873220
-31802337 -94326140
29901118 94629634
8981744...

output:

49501432.7022044
49504111.9000156
49506914.0037284
49504020.3841626
49500748.1808290
49509533.2816176
49504423.6514928
49503519.1264973
49507687.1662349
49501887.8451573
49501129.4738505
49506066.7849482
49503294.6517206
49500496.9255725
49503260.6522219
49510521.2321108
49504721.2793684
49511249.39...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 239ms
memory: 7228kb

input:

100000
74210313 -66772568
-82118759 55744795
-40558611 -90552265
-80801514 58093666
-87555090 46582002
-96330979 24086781
39402894 91628283
56594773 -82141487
39313600 91784698
89239441 43417687
-95774367 28264902
32961837 93669012
-85873036 -51077556
-27532569 -96083438
82705246 -55505999
-22508180...

output:

49506572.9114001
49507188.3698279
49504015.5868492
49502226.2551337
49511712.3791655
49508088.3725657
49508038.4721607
49511153.9459437
49503445.7644251
49505408.2422356
49501120.2191417
49504635.7946901
49501929.8603164
49500674.3593257
49508683.1372702
49503392.6527477
49501147.8083873
49507086.11...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 249ms
memory: 7344kb

input:

100000
-71207198 55424979
-79825607 -56036270
-83654833 37345395
-91097555 -17973035
-79663519 53088655
40943861 -91076400
84688501 31061641
-96431516 -1566452
-89205053 17120308
66023621 -67658770
-85253305 44553904
-95493219 -8941382
-79301859 45970085
-27319544 -90541866
-90379686 -10409784
-8376...

output:

45036750.1372239
45027842.8818136
45013570.7649709
45012430.8467587
45008268.5080021
45035953.6251027
45011940.3266864
45033497.6378687
45035993.0317809
45018438.5524731
45010458.6109156
45008354.7259052
45032420.0671344
45019612.3304008
45010086.5286970
45002868.3249786
45026600.6049201
45014785.35...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 236ms
memory: 7344kb

input:

100000
38905528 81237636
-87968422 -27436984
9608199 91019553
78087433 -61515160
-93465529 27267558
13655649 -92011700
-4844144 -90101777
-76856347 -55299593
7037669 95820739
73512631 -55423174
66171160 -69809341
-38015506 -91878674
92573512 18160315
-89558982 43574979
41250811 89067345
90892069 312...

output:

45035187.3884273
45009163.6065222
45033436.3931770
45019451.0239727
45022200.7504397
45014848.4584344
45024066.2168219
45004916.9090576
45009051.6157130
45011633.8119250
45006265.9086880
45025389.7773992
45018143.2059153
45004427.2401312
45017652.0731754
45025733.5626722
45032442.9115792
45037567.50...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 230ms
memory: 7192kb

input:

100000
73858871 59646768
74771059 50581404
69886208 66567485
-98824001 3209940
71195346 65729342
-31147238 89170502
-93247841 -18314860
25371727 94636356
96922565 192144
11319923 -96984253
-90534277 -37798172
92579912 22026541
-85805605 34201581
-34434706 84998535
28174675 -86301411
18885420 9491316...

output:

45004913.3664171
45049419.1160458
45013923.5129688
45018139.6488506
45036905.8127369
45014915.9261847
45021998.4164937
45005546.4190510
45013393.3187403
45031474.2617547
45023802.2902520
45024466.4821736
45028156.9922565
45028587.9272051
45021843.4432482
45015806.3953396
45019948.8055675
45006969.96...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 238ms
memory: 7360kb

input:

100000
6192364 97854354
-26396072 -87670473
-15829494 95984810
29977494 -87073709
85322761 44933323
-10724758 96451337
25075242 -88807937
88653656 -28596396
-7234959 97007100
-98015205 5615321
-46753278 -86423176
-84626507 -46187913
58215823 -70504834
88062585 26935126
79507695 56070039
-81885399 -4...

output:

45007894.8356611
45013616.1135625
45048543.6061462
45027729.0330648
45013317.4985194
45020005.9202679
45013214.4532615
45017977.1928253
45015065.2213867
45019880.1661493
45029719.3585012
45018055.1420110
45027958.6147321
45032293.0370836
45023771.4683761
45007361.3429901
45015632.3739848
45020279.06...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 238ms
memory: 7244kb

input:

100000
-56925997 -77019489
93686323 23015852
-96967479 14925388
-69298767 71247873
-89975226 -39629378
-81202105 -57862266
-30611438 -91102049
69779237 60415278
85454036 38912399
-23494246 -94997385
11333990 -97239874
26776076 95709458
7400584 -95188065
94132228 33609835
31334391 -91724795
15440367 ...

output:

45031230.0083619
45031012.6837546
45051159.9267533
45057523.9439006
45021248.9383935
45034531.5222573
45010861.9044017
45036940.6662584
45011332.8873037
45014214.3833544
45031679.2282824
45012785.3672063
45001127.1071562
45030055.9623051
45008553.3961224
45013926.0882915
45022274.1235793
45018793.87...

result:

ok 100000 numbers

Test #27:

score: 0
Accepted
time: 473ms
memory: 7552kb

input:

100000
86473583 -50222687
87983523 47527871
50172327 -86502810
-50052528 -86572186
-81465580 57994464
99757942 6953600
-89115446 45369999
-98572877 16834073
86724085 -49788872
-72244940 -69142374
95384011 -30031466
31730815 -94832244
-96383253 26650854
70233115 71185027
38343247 92356888
-76013019 6...

output:

49999997.4571804
49999998.4627794
49999997.1012831
49999996.8661267
49999998.6305340
49999998.5050833
49999996.2101661
49999998.6642196
49999997.4219625
49999996.6097953
49999997.2465503
49999997.5784507
49999997.7963024
49999996.7176689
49999998.5363129
49999997.8744430
49999997.4192269
49999998.77...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 471ms
memory: 7788kb

input:

100000
96098382 27660424
96993975 -24334494
98858570 15065921
-70174372 71242940
59401282 80445550
-34968800 -93686616
-45576276 89010123
-93157321 36355368
-98590008 -16733454
29170468 95650836
81074291 -58540220
92315133 -38443648
88517611 -46525596
99591182 -9033025
17031645 -98538935
-76791060 -...

output:

49999997.2281587
49999997.3025420
49999996.6710481
49999996.7132199
49999998.7399825
50000000.5315516
49999998.0506880
49999998.9604980
49999996.7553592
49999997.1424608
49999998.7725008
49999997.5903435
49999998.3012375
49999999.1442936
49999997.1038764
49999996.9476613
49999998.5665739
49999997.60...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 468ms
memory: 7760kb

input:

100000
98649054 -16381761
-99891340 -4660392
85079131 -52550367
98751502 -15752448
38325930 -92364069
16772724 98583333
75122377 66004758
95139156 30798377
-24102560 97051870
89328512 44949025
-83521481 -54992370
-22923261 97337161
-49154851 87085012
67965351 -73353320
-79586737 60547083
44791227 -8...

output:

49999996.8124151
49999996.7088924
49999997.6572201
49999997.0251825
49999997.5584498
49999997.9676562
49999998.1619127
49999996.5120548
49999998.4548825
49999998.2111204
49999998.4433880
49999997.0462428
49999997.1573697
49999997.0651830
49999995.5362256
49999997.6887904
49999996.5066466
49999996.90...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 471ms
memory: 7760kb

input:

100000
7197545 -99740639
39789850 91742935
-44563738 -89521349
92588284 -37781069
89874957 43846213
-97082384 23979340
52035210 85395169
87881876 -47715555
-25428031 -96713047
6688701 99776051
31394586 94944081
66622083 -74575443
81096253 -58509804
-98223145 18767345
10583592 -99438356
-97020186 -24...

output:

49999997.0242636
49999996.4351698
49999997.5472670
49999996.4184566
49999998.7878663
49999997.8148425
49999998.1209330
49999996.1151277
49999996.8872683
49999996.1102720
49999997.6365982
49999998.0198365
49999998.7855396
49999998.6437690
49999996.0682024
49999996.9319851
49999997.5245356
49999996.21...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 488ms
memory: 7928kb

input:

100000
48053189 87697724
-99230647 -12380496
71228034 -70189504
-99862038 -5250874
-92715593 -37467545
26308785 -96477183
91137520 41157649
86371053 50398812
-99541893 -9560913
-96837592 24949526
-28842311 95750301
-99906431 4324846
32704032 -94501032
-98983846 14219579
-98402231 17804504
42162900 9...

output:

49999996.0831309
49999996.4655374
49999998.4432053
49999995.6520979
49999998.1852534
49999998.4148445
49999999.0013581
49999997.2984746
49999997.1851978
49999999.0488719
49999997.2643069
49999996.6181675
49999996.5855972
49999997.8302104
49999997.6317785
49999998.2635080
49999996.4720499
49999997.37...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 405ms
memory: 7384kb

input:

100000
-23951830 97020265
-79900659 60056128
-83964098 54143803
97074821 23809857
61007903 79212713
-45094976 89223718
-89377964 44681664
-98513176 -17056240
-27426886 -96062608
56189487 82666265
18047227 -98345883
-99936265 1286532
18608822 98231586
-56949101 82157764
99503767 -8898358
52721687 -84...

output:

49951674.1879359
49951419.3102472
49951190.6025996
49951412.5821994
49951643.3201369
49952981.5404847
49951531.5661156
49950744.7078593
49951759.6741205
49952147.6803641
49950940.6456706
49951560.3948297
49951096.6605874
49952163.0136613
49952791.2038600
49952282.3186470
49951689.8356996
49951516.43...

result:

ok 100000 numbers

Test #33:

score: 0
Accepted
time: 422ms
memory: 7492kb

input:

100000
-82922797 55795521
98806631 15264719
27227855 96151671
90640250 -42064680
97570886 21814297
11561464 99312553
-63044255 -77522636
75253645 65715048
-46471655 -88525692
-74788283 66304581
59047518 -80664807
99509005 9753002
6599999 -99699054
-57520499 -81692754
-94724230 -32037998
-91266303 -4...

output:

49951008.8752197
49952120.1151772
49951313.8975322
49951522.6341237
49951493.4673222
49951417.8990498
49951239.5873103
49950786.0584495
49951126.6194570
49951635.2534672
49951599.4435538
49952120.2602651
49951396.9518225
49951843.5781771
49951084.2984792
49951715.9111628
49951821.1532902
49951695.86...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 367ms
memory: 7464kb

input:

100000
-94334950 -33002816
94253220 33387641
80851945 -58743434
92068179 38797643
92438296 38143230
87690855 47910947
18278347 98277620
98579284 16519538
87518221 48304789
-71902423 69487747
99868312 3214776
-74106386 67019802
-27751893 -96052705
-91146289 41016721
-98277121 -18367587
60051086 79947...

output:

49951455.3120065
49951491.3438154
49951164.1496551
49951630.0734803
49950857.0331885
49951496.7260943
49950560.2742411
49952262.7804620
49952389.1146194
49950986.9949467
49951582.7058412
49950722.7321049
49950989.4603775
49950398.0146354
49951306.4521628
49952072.1494008
49951714.7448141
49951776.54...

result:

ok 100000 numbers

Test #35:

score: 0
Accepted
time: 405ms
memory: 7352kb

input:

100000
66711064 74461687
-99974135 -2174163
-1056958 99918825
-36812938 92895057
40400128 -91384257
15553026 -98744225
51376353 85721836
98739904 -15613787
-99973461 1404943
14291417 -98963322
98599204 16637582
-92316397 -38311014
-51618501 -85635835
-36591459 -93015393
-91664061 -39878690
99771335 ...

output:

49950743.7254164
49952335.5206178
49951444.8852714
49951226.6904486
49951463.9623629
49951443.5648730
49952105.3892571
49951524.8219949
49951689.4897814
49951151.8564956
49951874.8125918
49951645.9768621
49951281.2548604
49951413.4285631
49951150.7229189
49951623.4420294
49951210.6615923
49951075.60...

result:

ok 100000 numbers

Test #36:

score: 0
Accepted
time: 370ms
memory: 7304kb

input:

100000
-50274904 86430058
-30033231 -95322369
-98405889 17641407
-61672858 78646085
26241959 96398065
4426523 99837644
-99019995 -13814286
99913840 681111
90361534 -42631803
87161706 48939878
-95813074 28347212
-40705166 91264788
98666969 16193024
85025293 52491476
-3692790 -99876257
-73433772 -6783...

output:

49951659.9885079
49950981.3209608
49951893.0069188
49952278.5161718
49951380.7045542
49950845.5129634
49951575.7730340
49951240.9648802
49951205.7488277
49951032.1517310
49951732.0788584
49951938.7185009
49950923.6301759
49951266.0488254
49950795.5181505
49951319.3305335
49951706.1207406
49951663.83...

result:

ok 100000 numbers

Test #37:

score: 0
Accepted
time: 332ms
memory: 7252kb

input:

100000
-3329385 99331174
-70604294 70669786
-87081417 -47338605
67572485 73507498
-94011626 -33780311
-11304772 98491936
40610638 90325570
-59981987 -78948235
-25072291 -96778665
97190682 -18875941
73326816 67610572
71253553 69607148
63274218 -76228295
40643832 91311687
31058993 94112669
96614227 -2...

output:

49504623.1938576
49506835.2408185
49505169.5804012
49508592.1212292
49509011.1218333
49505380.6373267
49504969.0347028
49503721.1126447
49502895.1142387
49508793.7919138
49505050.2430741
49506657.7121537
49507735.1604685
49502361.4840257
49508087.7087030
49504477.7230501
49509939.3582995
49505710.82...

result:

ok 100000 numbers

Test #38:

score: 0
Accepted
time: 364ms
memory: 7288kb

input:

100000
-88188547 -45804127
35518984 -92836002
84909347 -52102417
-78092577 -61565961
53608303 -83757017
-43358191 -89594529
-99733872 -5307764
51833620 84616172
-58956000 80333018
-44663911 -88660327
39476608 -90966406
98023033 -15767254
-92649608 36189499
-20044268 -97062782
75271019 -64531120
1305...

output:

49505594.9236759
49509390.1400757
49506149.0899781
49510170.0927458
49503968.5552830
49506197.3326305
49507042.6411098
49505615.6400179
49510195.1001031
49506434.9740628
49507114.5427643
49507814.9278767
49508422.6810742
49504711.5242513
49506397.0885453
49508045.9339595
49510339.8756964
49504888.56...

result:

ok 100000 numbers

Test #39:

score: 0
Accepted
time: 372ms
memory: 7384kb

input:

100000
-99782597 -3415872
-61105726 79084288
30912116 -94584503
26277091 95534616
-99475895 -2777059
25739063 95981962
-29397062 94756672
13419054 -98397843
75908620 65036189
-95649393 -29121947
-99476677 -4608633
-44872944 89131709
58443026 -80934109
-80216834 -58992281
-99642474 -4043864
-93282892...

output:

49507920.8302028
49503935.8735004
49504166.4472332
49506478.4563929
49506103.9466172
49506818.7894118
49505185.2773858
49507164.5004687
49507676.9478490
49506327.9705427
49505482.6306197
49507856.9061263
49508781.7658686
49509721.3195093
49505347.4988808
49505364.1912617
49509871.4989426
49504787.86...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 392ms
memory: 7400kb

input:

100000
-36117371 92618778
-73335258 -67061989
-80911383 57489284
89176933 -43555438
-44254978 89569042
-86787265 -48709508
-97251076 20319527
11571957 99298949
70511170 -69837542
-99634170 482767
96836213 22314925
92257812 36998150
55392610 -82618881
64718586 75192210
-33320217 93286849
71138573 702...

output:

49507470.5102520
49504173.7449605
49508449.7276101
49507818.3199970
49503991.5868418
49507051.0852813
49507825.0110924
49507882.6397741
49509928.8612812
49503373.4930668
49504658.5253268
49507126.8005136
49504450.0872117
49508921.0961942
49505989.4778772
49505366.3131397
49506878.6651441
49506176.33...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 373ms
memory: 7340kb

input:

100000
-19955231 -97699535
94825749 -28990747
-79907148 -59107167
-99027556 1423520
37739298 -92055126
84889533 -52160862
-68994023 71800045
-78602361 61152977
-41135006 -90230500
-18711359 -97257627
66663581 74134831
-37980361 -92135750
-2196230 -99805345
61435279 78416798
99254865 5765553
9861983 ...

output:

49509084.9552790
49509044.5589488
49508051.3976997
49506403.0937439
49509646.0058207
49510964.9010520
49504435.0629076
49503658.3724903
49508600.5934109
49508992.9808276
49506743.6986766
49503939.7035901
49504163.5735945
49508136.4803242
49505622.8908843
49505517.7993199
49506417.6137585
49504591.44...

result:

ok 100000 numbers

Test #42:

score: 0
Accepted
time: 345ms
memory: 7428kb

input:

100000
92556374 12072350
93766905 4825190
-67271877 69890083
73298299 55897595
-31299356 -93814485
-80498315 54176779
-31345062 -88453539
83029787 -49705175
-80101942 -52307613
-69888580 -56945797
-85803388 38619155
63351605 70575401
93281896 22216160
-97847849 -20164083
76241863 52328510
-95583679 ...

output:

45013832.1076685
45018190.6915386
45016655.1065457
45020233.0857539
45026293.8037958
45061276.3205336
45038673.0572490
45026156.2575883
45013595.7430777
45025686.7959728
45037303.2716239
45028239.0289746
45020299.2964048
45023715.7638952
45020242.1871600
45042441.8549472
45028448.4434257
45029501.95...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 376ms
memory: 7192kb

input:

100000
-32081572 90116995
-73229798 -64672076
91131427 5196295
10394383 -94678607
99786071 639864
-92342810 -852711
-84391341 -47449093
-74420874 64181438
-51777172 -78771868
-76271622 48551648
89768757 12110773
-67381897 -60367678
74807369 -64148569
48356402 -76298700
-1187892 -93943444
-93924469 -...

output:

45043971.6672017
45037044.3237821
45039953.5258940
45049333.1323074
45029998.0054949
45024418.3487864
45033727.9389797
45040087.4147926
45027614.9067239
45044037.7991884
45021590.2847209
45032495.2682304
45024798.5251681
45019386.4142480
45024119.8119076
45013311.9709241
45035672.4392273
45031196.84...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 380ms
memory: 7424kb

input:

100000
9559919 92659433
51875371 83680106
78642333 -59484990
-67562834 73384342
-50641362 -85443942
94239770 18902122
-63150344 66462007
93871387 -2488444
-78837743 43705750
-18631355 94166502
-21600045 -92649401
96280408 -20960957
-26104161 87813365
-16304015 -96036171
-66451374 73268709
-535780 -9...

output:

45035085.1285767
45032579.5419530
45039705.6764855
45027911.2698470
45032692.0402884
45040422.1855027
45026712.8618487
45031226.4947403
45015448.0927643
45020328.5633668
45038180.4037778
45031725.3324958
45020332.4111618
45025772.0380055
45034324.3322298
45023424.8558298
45053963.5587543
45038847.79...

result:

ok 100000 numbers

Test #45:

score: 0
Accepted
time: 346ms
memory: 7272kb

input:

100000
63951077 -71761548
73763706 64396798
21419213 95263455
-68397093 68002102
-62901958 67448916
56595081 -71927093
-85235758 37748571
-63653511 75097403
-68746842 61306045
13699376 92719471
-39604640 -84729019
30466785 90338708
-89960990 10977635
65876081 -64868424
-42437656 -83596792
-68055453 ...

output:

45024619.4574575
45022447.0127799
45022571.2617215
45022725.3194232
45017987.7461518
45021932.5050704
45035073.1008263
45020086.9484457
45017427.0789492
45014614.0089426
45023853.3685528
45040989.6071098
45012689.0889144
45015942.9494709
45028884.7561760
45014805.4317334
45018403.2933179
45041397.99...

result:

ok 100000 numbers

Test #46:

score: 0
Accepted
time: 340ms
memory: 7192kb

input:

100000
-15226924 97699217
-88190354 29200235
-82332756 49054626
92982578 -33157210
59227929 -73138724
38249741 91550174
-51100484 82504881
-96377839 -15349299
36198347 91856588
-90519618 31198671
16179809 -91684442
42535161 -83090574
-70289671 63418188
70901869 -63653069
-71694352 67433238
-8028358 ...

output:

45038361.4085142
45025634.8959464
45036750.1804423
45030721.8290839
45024194.5498084
45040922.8801917
45032333.1125981
45038384.8171094
45031476.9762935
45032198.6631958
45038419.1376384
45037035.0191930
45022000.8605776
45017701.7815514
45027831.5414370
45031054.6550204
45028462.5769713
45021359.62...

result:

ok 100000 numbers

Test #47:

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

input:

200
40 51
52 66
16 -57
25 -86
-68 -21
-77 -23
67 39
62 36
-70 -59
-41 -34
-20 70
-22 77
-16 -82
-19 -95
-77 24
-73 23
-84 46
-78 43
-12 55
-20 93
52 -52
47 -47
-76 18
-76 18
-42 25
-76 45
78 -13
62 -10
86 -37
66 -28
44 60
58 80
-58 -25
-62 -27
-52 82
-36 57
84 13
85 13
-93 13
-49 7
-37 87
-22 52
-52...

output:

25.0980450
27.6807695
35.1612973
33.4051880
26.1910262
25.7627016
29.2122627
27.9898898
27.2367533
25.8700686
26.5637197
24.8387497
25.1733596
27.8803287
26.4061010
30.4346558
29.4939520
32.1622855
25.6009478
26.1046413
33.3829766
26.5936922
25.8024918
24.8500536
29.4994822
27.2969364
25.6526383
25....

result:

ok 100 numbers

Test #48:

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

input:

203
82 0
66 0
85 0
-38 45
-57 68
-1 71
-1 80
73 25
68 23
-18 90
-10 52
45 57
50 63
-39 74
-45 85
19 78
18 74
31 91
28 85
36 43
61 73
-58 44
-53 40
16 77
16 77
16 47
29 83
-73 30
-58 23
-82 44
-63 34
65 36
86 48
-4 63
-4 67
50 83
35 58
84 14
85 14
15 92
8 49
54 77
32 46
-26 85
-29 95
67 60
74 66
89 4...

output:

25.4084632
59.2852656
36.6149573
25.6357660
25.1927908
29.9351121
27.5867238
25.4624857
43.1097175
24.8716165
150.9910870
27.8770140
28.5227369
25.0630333
24.9687052
25.1195267
62.8249282
25.0762532
27.7124657
25.7920419
27.6548410
27.6002984
25.1953031
45.3176907
33.8612332
57.9750904
26.1725955
27...

result:

ok 100 numbers

Test #49:

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

input:

500
-55 23
-64 27
-61 26
-56 23
-92 38
-90 39
-81 35
-48 21
-73 31
-45 19
-1 -53
-1 -68
-1 -68
-1 -85
-1 -88
33 -59
35 -62
25 -45
31 -55
32 -57
-1 70
-1 92
0 51
-1 69
0 54
0 -72
0 -94
0 -49
0 -56
0 -49
79 -40
73 -38
44 -22
44 -22
50 -26
-64 45
-50 35
-40 28
-54 38
-63 45
-70 25
-67 24
-64 22
-89 31
...

output:

24.8160434
25.2171914
25.6442830
24.7074263
25.4244822
24.9864971
25.1934837
25.1424050
24.6632653
25.9403026
24.6549066
26.1047319
25.0361490
26.1098521
25.2500000
25.9624056
24.8650861
25.9129471
25.4879830
25.6555169
25.5235015
26.2785525
25.5048859
25.6010631
25.3106955
25.5688409
24.5016954
25....

result:

ok 100 numbers

Test #50:

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

input:

503
57 0
60 0
70 0
48 36
79 60
74 56
78 59
70 53
-36 71
-22 44
-39 75
-24 47
-31 61
-75 41
-77 43
-78 43
-59 33
-62 35
-47 43
-48 44
-44 40
-52 47
-68 62
57 39
45 30
78 53
60 41
78 53
-6 56
-5 49
-9 80
-10 88
-9 82
-19 46
-22 52
-27 65
-30 72
-24 57
54 38
63 44
59 41
61 42
59 41
74 58
69 54
42 33
58...

output:

262.7184805
24.9423338
25.4000775
35.6455904
25.6785267
24.8889101
97.5303354
40.8609414
104.9696201
24.6462756
30.4478566
25.1798528
25.2245240
24.6462756
24.7329043
25.2963029
24.6275343
24.8863905
26.1528659
-1
24.6285373
50.5148522
412.4484421
25.1734544
25.7372128
24.8119267
27.4962989
-1
25.03...

result:

ok 100 numbers

Test #51:

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

input:

1000
35 76
32 70
29 63
29 64
33 72
34 74
32 70
35 76
40 89
41 90
14 89
10 66
12 72
12 76
12 72
12 72
9 54
9 59
11 68
12 76
-35 75
-39 83
-39 84
-21 45
-22 46
-26 56
-37 79
-24 52
-26 56
-23 49
80 -14
66 -11
98 -17
73 -12
94 -16
93 -16
60 -10
73 -12
97 -16
95 -16
23 -46
41 -82
27 -54
26 -52
34 -67
24...

output:

24.8702895
25.1015653
24.9336003
25.2237933
24.6638099
25.5296681
24.6884882
24.8860397
24.9859763
25.1298340
24.8246200
25.1262909
25.6490185
25.2037917
25.0230398
24.6962692
25.2494917
25.4407083
24.4391214
24.9235010
24.8295042
24.8250246
25.1687956
24.8295042
25.0571414
25.6152483
24.8969606
24....

result:

ok 100 numbers

Test #52:

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

input:

1003
62 0
84 0
78 0
69 13
78 15
80 15
76 14
82 15
96 18
98 19
53 10
89 17
65 12
-19 75
-18 71
-18 71
-13 53
-14 58
-17 66
-19 75
-19 75
-20 80
-22 89
-44 22
-46 23
-55 27
-78 39
-51 25
-55 27
-49 24
-53 26
-73 36
-59 29
-50 55
-64 70
-63 70
-41 45
-50 55
-66 73
-65 71
-34 37
-35 38
-61 68
-52 27
-67...

output:

24.6916132
44.6688630
24.5350294
24.5498291
59.8128112
24.5971190
24.6820054
24.5234819
24.6172925
53.1816455
24.5270295
25.1796937
25.1394445
29.6312290
24.7673899
25.3575553
25.1053790
47.6403253
24.5544309
24.9349688
24.9127287
32.7337677
-1
147.5368210
25.1105800
41.6951879
24.9652527
24.6820054...

result:

ok 100 numbers

Test #53:

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

input:

200
9 93
5 51
-53 -17
-93 -30
-55 -30
-52 -29
91 -15
88 -15
56 -49
41 -36
14 -87
11 -65
60 51
73 62
-58 -25
-87 -37
-70 2
-96 3
38 -49
52 -68
74 42
56 32
-72 -19
-93 -25
-18 -50
-29 -83
1 -91
0 -81
84 -29
51 -18
-63 64
-42 43
-7 49
-9 57
45 29
46 29
33 -41
37 -46
92 -35
92 -35
23 86
17 63
75 -20
83 ...

output:

28.8632169
29.5788791
26.7833686
26.8931473
26.7030692
28.0818182
30.6077352
26.9569762
27.7629202
27.9730371
28.8600873
29.3697021
26.6056363
31.2871334
27.6716559
27.2337719
27.0666564
29.8152897
25.5806545
26.3548872
27.0922734
30.0541179
25.9786694
28.1943362
27.2518695
26.5711816
31.5634282
26....

result:

ok 100 numbers

Test #54:

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

input:

203
90 0
94 0
52 0
-1 55
-3 97
-7 62
-6 59
-86 35
-83 33
-60 44
-44 32
-53 70
-39 52
72 31
89 38
-4 63
-6 94
8 70
11 96
-47 41
-65 56
81 27
61 20
0 74
0 96
-22 49
-36 81
-50 76
-44 68
-79 39
-49 24
39 80
26 54
32 37
38 43
50 18
51 18
-40 34
-45 38
-88 45
-88 45
70 55
51 40
-71 32
-78 35
-30 52
-30 5...

output:

27.0081463
28.6764706
28.2400000
27.7811204
27.9637968
161.5249240
28.6000000
26.8560980
61.1592459
-1
28.7983812
26.5707979
2844.4209444
29.4547844
26.2159694
25.8200422
25.6806875
39.0893791
27.0424443
27.5591356
27.5331200
27.5184475
27.5090909
27.3797189
27.4042604
26.8933042
75.9659461
42.08334...

result:

ok 100 numbers

Test #55:

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

input:

500
-62 -10
-87 -14
-59 -9
-56 -9
-58 -9
-88 17
-66 13
-68 13
-68 13
-65 13
86 10
95 11
57 7
51 6
72 8
10 63
11 71
11 70
11 71
12 81
-44 83
-23 44
-32 61
-35 67
-44 83
81 -22
65 -17
76 -20
76 -20
88 -24
25 90
22 79
23 82
17 59
14 49
-85 51
-60 36
-59 36
-70 42
-57 34
48 71
34 51
43 64
29 43
42 62
60...

output:

26.8593745
26.4708660
26.0421259
25.2079163
28.2370550
27.1189199
26.7777017
26.6496278
27.4384707
25.5797970
25.2755910
25.2556981
27.0221321
26.4216591
25.5578815
27.2833044
25.0993971
25.5863896
27.8750786
25.0886930
25.4483391
26.8829161
24.5221846
27.4787623
24.9851773
25.5116715
27.9403712
25....

result:

ok 100 numbers

Test #56:

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

input:

503
66 0
63 0
89 0
-51 23
-53 24
-53 24
-81 37
-61 28
-12 68
-11 65
-16 91
-15 85
-16 94
17 48
24 68
19 53
21 60
24 67
-65 30
-75 34
-82 37
-86 39
-45 20
-41 63
-52 79
-47 72
-46 71
-37 56
-25 74
-29 86
-25 73
-30 88
-27 78
12 60
10 49
18 92
20 97
14 69
28 76
23 62
17 47
29 80
21 58
-47 21
-68 31
-6...

output:

29.1983816
25.4146242
222.7386361
31.0899997
53.6596345
26.0777442
-1
62.3625388
25.3501645
25.1106714
26.3838608
26.9394122
30.2412167
28.8690849
25.9193151
24.6786214
31.2137522
24.6846212
70.3661902
26.5733332
25.7595216
26.2459062
25.2990711
25.4665802
42.3573513
30.4857513
93.3440379
24.6722856...

result:

ok 100 numbers

Test #57:

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

input:

1000
-8 60
-12 96
-8 61
-8 66
-11 87
-9 69
-9 68
-8 62
-8 62
-8 63
-17 70
-17 71
-12 48
-22 91
-22 88
-14 57
-24 97
-13 54
-16 66
-17 68
44 23
62 32
81 42
51 26
61 31
59 31
68 35
66 34
66 34
47 25
50 16
55 18
91 30
51 17
90 30
76 25
69 23
64 21
66 22
63 21
-94 21
-55 12
-74 16
-86 19
-85 19
-93 21
-...

output:

25.3801326
25.9693245
25.8689752
25.7984762
26.4425057
25.3553253
24.6792217
24.9245300
25.1042963
25.7649271
25.6102761
24.7634893
26.3975448
25.9401483
25.3802578
25.6654058
26.4638877
25.0938544
26.1905483
25.4457014
25.1297213
25.5002756
25.9816039
25.4463994
25.2005169
25.5363200
26.4004550
25....

result:

ok 100 numbers

Test #58:

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

input:

1003
70 0
61 0
97 0
-42 52
-55 68
-44 54
-43 53
-39 48
-39 48
-40 49
-45 56
-45 56
-46 57
-88 30
-86 29
-55 19
-94 32
-53 18
-65 22
-67 22
-81 27
-47 16
-67 22
27 50
33 60
32 58
37 67
36 65
36 65
26 47
29 53
25 46
28 51
50 18
89 32
76 27
68 24
63 23
65 23
62 22
80 29
91 33
53 19
-41 78
-40 78
-44 85...

output:

124.2466037
25.1655078
25.0487525
30.2964132
64.8484562
24.7851410
30.8486467
48.2559998
61.3382186
119.7627331
-1
48.1146719
25.3600000
25.1012271
32.4424040
26.0056533
24.8246345
40.5520740
25.3157298
25.1000384
25.2808704
25.0134336
25.5325015
24.8181841
25.1104329
25.3619136
25.8058532
46.569824...

result:

ok 100 numbers

Test #59:

score: 0
Accepted
time: 407ms
memory: 7500kb

input:

100000
41594617 -90874202
41616553 -90922126
41579076 -90840249
41587678 -90859042
41603508 -90893628
41611148 -90910318
41610867 -90909704
41585149 -90853518
41611061 -90910128
41600233 -90886472
-41392157 90946563
-41394053 90950728
-41405020 90974825
-41387761 90936902
-41423060 91014461
-4141407...

output:

49952220.5807725
49951771.6770449
49951371.9893360
49951722.4530878
49951600.6241232
49951055.4109790
49951961.6412743
49951445.7744755
49951409.2811148
49951768.2373736
49951956.1813357
49950601.8756955
49951790.3266162
49951730.7155938
49950967.2527117
49951997.8780043
49951189.4592747
49951928.55...

result:

ok 100000 numbers

Test #60:

score: 0
Accepted
time: 300ms
memory: 7180kb

input:

99993
99923917 0
99924571 0
99937757 0
-23163715 97243691
-23162127 97237022
-23153610 97201267
-23162718 97239503
-23151418 97192067
-23157394 97217155
-23162408 97238202
-23153027 97198819
-23160206 97228957
-23166709 97256258
-27227991 96159791
-27243429 96214310
-27237920 96194854
-27225082 9614...

output:

49950676.4874895
104318412.7586585
82053691.1775917
49950848.4959955
-1
62823858.0887818
49951164.2282362
50952144.1299400
49950710.1752451
2562289954.4436688
87290985.0552721
49950530.3264595
-1
53452189.1339143
-1
49950365.0065749
50726280.4353200
94580293.2776737
78191634.7169583
94586072.3123092...

result:

ok 100000 numbers

Test #61:

score: 0
Accepted
time: 258ms
memory: 7320kb

input:

100000
17236606 98488167
17233116 98468222
17228331 98440886
17232758 98466177
17231878 98461152
17231411 98458482
17222609 98408189
17235073 98479406
17225005 98421879
17233979 98473157
66868196 -74259692
66872083 -74264009
66886995 -74280569
66874697 -74266911
66881412 -74274369
66859821 -74250392...

output:

49950400.5839320
49951113.1033806
49952554.3327271
49951016.6225045
49951981.6467437
49951323.6891307
49951016.7356803
49952086.3026999
49950219.5919243
49951676.9871695
49951340.9940696
49950491.0388671
49950926.1342676
49951133.2805535
49951106.5999780
49951200.7264014
49950108.9869111
49951666.89...

result:

ok 100000 numbers

Test #62:

score: 0
Accepted
time: 232ms
memory: 7312kb

input:

99993
99972481 0
99935818 0
99941457 0
95115106 30556139
95193853 30581437
95202874 30584335
95192329 30580947
95147223 30566457
95183244 30578028
95182967 30577939
95190044 30580213
95188511 30579720
95162235 30571279
34715168 93756807
34705128 93729691
34720761 93771913
34700598 93717457
34699848 ...

output:

49950344.3636963
50383244.8980588
49950240.0072633
49950656.4694629
49950335.7150594
92431763.6937951
51224242.3295757
49950631.1462176
484250533.0632749
49950493.7316514
49950237.9749466
62215523.3577955
49950759.8816187
49950680.3840496
72516452.8659844
49950436.2629666
49950204.9708143
50872549.0...

result:

ok 100000 numbers

Test #63:

score: 0
Accepted
time: 361ms
memory: 7352kb

input:

100000
12687496 -91994997
12824312 -92987026
13317803 -96565251
13299688 -96433902
12720209 -92232193
13542850 -98197029
13074398 -94800361
12545291 -90963892
13229962 -95928329
12969350 -94038672
-48673482 84982797
-45021449 78606431
-45441747 79340261
-46482111 81156714
-49368630 86196511
-4759406...

output:

45050534.9775924
45031402.7405407
45058668.0197665
45033346.3674831
45030976.4817313
45016979.9796989
45028401.8810623
45021884.5377100
45028879.9866637
45040530.2163176
45040983.5530843
45031232.2778025
45026102.8970949
45034367.4372642
45030069.4306419
45017441.2835450
45030424.0509298
45019519.45...

result:

ok 100000 numbers

Test #64:

score: 0
Accepted
time: 325ms
memory: 7248kb

input:

99993
95502024 0
91716495 0
93035290 0
72077807 60990245
73843982 62484734
71147783 60203284
70213842 59413009
76122586 64412825
75950793 64267459
70790432 59900904
70968931 60051945
74087858 62691094
74591423 63117197
-60476742 71946579
-62742047 74641515
-58551774 69656528
-63266536 75265477
-5829...

output:

65733201.0707420
45023455.6965423
45014395.9001700
47149047.4557271
45014289.1781607
45018390.3390819
55468012.0962475
54515884.3215919
69269766.5937204
65741869.3378003
45011260.7521514
45013931.8266115
45027567.9286370
45039013.5204298
80066785.8375092
45898960.7039469
45014963.3611588
45026726.34...

result:

ok 100000 numbers

Test #65:

score: 0
Accepted
time: 244ms
memory: 7396kb

input:

100000
42239570 84097913
40467871 80570506
44226575 88053991
40847944 81327222
40619575 80872544
44389877 88379120
42783412 85180690
40891805 81414547
42268186 84154887
41491942 82609406
73479752 -67728993
69659672 -64207884
70858995 -65313344
71508900 -65912386
69056997 -63652376
71008080 -65450762...

output:

45013524.0640211
45020398.7656001
45019955.6471926
45008672.1921625
45017581.5665665
45010581.7339772
45013856.7514872
45012629.0191479
45016784.9746403
45011523.2878575
45026949.6634180
45026007.7647798
45018574.5536488
45024474.4795329
45012557.1394634
45006378.3329360
45027582.4593794
45015349.78...

result:

ok 100000 numbers

Test #66:

score: 0
Accepted
time: 271ms
memory: 7508kb

input:

99993
96817884 0
92960446 0
94106286 0
-33154491 86737124
-33608115 87923875
-33196444 86846880
-32705929 85563620
-33550638 87773506
-34572794 90447619
-34019689 89000613
-33108878 86617795
-35297179 92342720
-34664558 90687688
-6326254 92273893
-6316622 92133389
-6606001 96354241
-6694254 97641488...

output:

45025599.0601631
45010203.0927176
45016437.3093483
45006467.8550141
131742656.7725028
46980361.8293544
80973529.2432913
52921873.4666583
45011842.8843788
68504825.0616140
45018861.0515193
59853174.1557963
59496860.4174862
71137140.2858089
69404093.6005591
45419042.8674222
45006335.2931616
435485905....

result:

ok 100000 numbers

Test #67:

score: 0
Accepted
time: 377ms
memory: 7276kb

input:

100000
-54553504 -83466397
-53217438 -81422228
-51401674 -78644124
-53757138 -82247964
-53403130 -81706335
-54001247 -82621449
-51670298 -79055116
-54267073 -83028160
-51905316 -79414692
-52078219 -79679232
-52023670 -79595772
-50932231 -77925880
-53690814 -82146489
-54567725 -83488155
-51286909 -78...

output:

45049274.7608778
45035096.8537957
45026791.0454171
45029899.2833552
45029865.2894790
45044294.7701691
45015654.4181946
45041224.6847061
45033658.7823966
45015206.2866537
45032305.8972297
45041809.5075904
45031745.0456340
45023243.8834512
45030383.3286296
45029832.3532626
45036620.7836758
45030176.67...

result:

ok 100000 numbers

Test #68:

score: 0
Accepted
time: 313ms
memory: 7068kb

input:

99903
94448229 0
90761763 0
97985588 0
89901191 14452033
97883093 15735161
90118625 14486987
95578572 15364698
94701726 15223741
98448883 15826114
92212912 14823653
94215840 15145633
95077988 15284227
91419317 14696079
91425707 14697106
90844976 14603751
98587220 15848352
97841999 15728555
91363965 ...

output:

45011299.7432543
134372110.0542201
45014323.9347485
45013925.5732135
45199650.7069378
47433053.8517437
-1
179514912.4773604
45024826.5968423
45018053.6683542
45013564.3147946
45020087.0812146
45023353.3642511
187685563.8983114
45018822.4061010
-1
86547804.3101663
45090789.7547013
45019168.7184213
31...

result:

ok 100000 numbers

Test #69:

score: 0
Accepted
time: 236ms
memory: 7188kb

input:

100000
88804287 36439715
86562171 35519691
87659885 35970124
89457475 36707742
83298350 34180423
91106060 37384218
91620802 37595437
90862639 37284334
85069690 34907271
85764475 35192367
92170179 37820866
87796542 36026200
85616339 35131581
87350464 35843157
90172873 37001297
89474600 36714770
90840...

output:

45025630.7338847
45016999.1407902
45020400.7283336
45037891.7342361
45045272.8010039
45009662.0720252
45038911.4381611
45024442.0488517
45021030.9468095
45043493.9626652
45031010.4706786
45017259.8968520
45057873.6377957
45029140.5477420
45007418.0812072
45025627.9584522
45011091.6157514
45017002.04...

result:

ok 100000 numbers

Test #70:

score: 0
Accepted
time: 229ms
memory: 7464kb

input:

99903
95572601 0
92262610 0
94280776 0
17594269 97925670
17071048 95013545
16101053 89614772
16162408 89956264
16801040 93510741
17116697 95267616
16966675 94432627
15954553 88799389
17348696 96558871
17153395 95471867
16358027 91045032
16040142 89275758
17578486 97837828
16743413 93190002
17196216 ...

output:

78834094.0361865
45349195.0501640
45171861.5025769
48480891.2220246
45009700.9962924
45055519.3038752
53401156.2798114
45007886.0118600
45002321.0308878
237333132.9838363
45004216.4378640
45016230.6974558
45015011.0378342
45004955.1216323
45007950.6161545
48938262.3248439
50030735.0974226
45007508.1...

result:

ok 100000 numbers

Test #71:

score: 0
Accepted
time: 266ms
memory: 6772kb

input:

100000
90980678 90980678
-90980678 90980678
90980678 -90980678
-90980678 -90980678
90980678 56516627
-39032083 90980678
-90980678 -67650282
90980678 77163629
57789179 90980678
-90980678 -60740012
-90980678 -46397517
25299242 90980678
-1387583 -90980678
9324008 -90980678
-90980678 47716991
90980678 -...

output:

45454659.8830251
52267721.0949333
47567301.4165599
45835920.4892062
45281217.3320670
49497507.4403074
51087067.3972036
47211961.4669473
49979164.3011098
47194779.2571502
50877841.0260503
45886964.4134848
45659783.2572532
46666472.0335007
46848634.4928513
49623792.6952423
46838451.4108795
47980782.33...

result:

ok 100000 numbers

Test #72:

score: 0
Accepted
time: 432ms
memory: 7248kb

input:

100000
90964825 90964825
-90964825 90964825
90964825 -90964825
-90964825 -90964825
66922048 -90964825
-3433934 -90964825
90964825 -65962488
-35699201 -90964825
-64781820 -90964825
-68303343 -90964825
-90964825 -11834307
-90964825 -75592444
61554274 90964825
-90964825 -65419756
-90964825 -83227577
-2...

output:

52506632.9411709
48917742.2433202
45730847.9844045
46625710.2538794
45894715.5302422
46243303.9184774
46323847.8251029
51857953.7106286
50701807.7602210
53111418.4215916
53185499.0273624
49541798.4368138
48782381.5436496
46126166.8516916
51463817.9565056
47348810.2248074
47523041.5706571
48089260.42...

result:

ok 100000 numbers

Test #73:

score: 0
Accepted
time: 171ms
memory: 6940kb

input:

100
94620051 94620051
-94620051 94620051
94620051 -94620051
-94620051 -94620051
19629451 -94620051
39482667 -94620051
80264366 94620051
73728319 -94620051
94620051 -8757638
-94620051 48404092
97294526 97294526
-97294526 97294526
97294526 -97294526
-97294526 -97294526
74085262 -97294526
97294526 5339...

output:

57058690.5873584
58750526.7170771
53921471.6114118
48054800.0638518
51388953.7726174
53049592.9487737
50255976.6856611
51611646.5216844
49085978.9030774
49986287.6034015
57564532.4936764
53389743.1069165
51263620.2503186
47818554.7950521
55469541.8433357
48783405.7204230
56347660.1921494
48352726.76...

result:

ok 100000 numbers

Test #74:

score: 0
Accepted
time: 189ms
memory: 6684kb

input:

100
96939842 96939842
-96939842 96939842
96939842 -96939842
-96939842 -96939842
96939842 9467761
72127104 -96939842
-90892367 -96939842
92642617 96939842
-96939842 -3094298
82157644 -96939842
98980503 98980503
-98980503 98980503
98980503 -98980503
-98980503 -98980503
98980503 29737792
40467990 -9898...

output:

59832159.8365840
56789627.0423192
58605753.9200867
56241909.2553724
58403522.0637230
49867276.6070748
53771735.3832920
60878114.6120462
65403126.5516145
60385174.3169507
52834342.7179392
56640040.6244990
57515466.0745165
51278302.0823657
58653062.9318082
57705635.7576239
55440268.4439115
58802790.75...

result:

ok 100000 numbers

Test #75:

score: 0
Accepted
time: 191ms
memory: 6328kb

input:

10000
98738384 98738384
-98738384 98738384
98738384 -98738384
-98738384 -98738384
98738384 -22669726
98738384 -57747390
54319739 98738384
-12312798 -98738384
-45545728 -98738384
-98738384 901349
99911171 99911171
-99911171 99911171
99911171 -99911171
-99911171 -99911171
74948172 -99911171
-99911171 ...

output:

49188554.5716550
46958060.0143506
45863802.9493654
50306854.0210014
46668429.3058183
52705395.0631661
52873900.9345917
52514950.4219975
52575642.5149521
48850843.5111387
48330406.9893539
47369837.8276599
50582138.7499193
51929332.5739225
49899005.5120347
52302378.1580503
52604629.9601667
51189092.71...

result:

ok 100000 numbers

Test #76:

score: 0
Accepted
time: 307ms
memory: 6756kb

input:

10000
96091308 96091308
-96091308 96091308
96091308 -96091308
-96091308 -96091308
4375227 -96091308
96091308 41088450
-96091308 -26224158
38116835 96091308
17474983 96091308
-96091308 69402616
99261504 99261504
-99261504 99261504
99261504 -99261504
-99261504 -99261504
99261504 -85669909
-92897330 -9...

output:

50724068.3823508
46801711.8249329
46674376.9164714
48909144.5215956
52909623.9018947
53004479.1263407
49661466.4193415
49370888.0708044
52436940.4800760
51923930.9500075
45244547.9434835
46351287.2216960
48167529.3834429
46641515.8122306
45379267.6663667
50761995.5735808
47061050.8123678
47127706.90...

result:

ok 100000 numbers

Test #77:

score: 0
Accepted
time: 106ms
memory: 5696kb

input:

16
92745291 92745291
-92745291 92745291
92745291 -92745291
-92745291 -92745291
-60558247 -92745291
92745291 1929378
-58460896 -92745291
-92745291 -74454813
-59173372 92745291
-48562718 92745291
92745291 -53804670
78260613 92745291
-45079729 -92745291
92745291 42058113
2338714 -92745291
-92745291 -29...

output:

89337940.6383037
59140564.8412467
60797197.2508570
55026722.4199240
57981311.2465901
67061094.8350036
65972052.6269025
76743936.9091993
81881611.8233651
56558247.6286641
51620749.4492294
56964033.1841272
73545017.8452876
133429846.9312586
67627378.0302955
235259967.5306902
64233046.1129860
196659407...

result:

ok 100000 numbers

Test #78:

score: 0
Accepted
time: 128ms
memory: 5832kb

input:

16
97696305 97696305
-97696305 97696305
97696305 -97696305
-97696305 -97696305
464073 97696305
-97696305 -18165588
1235320 97696305
97696305 -13186754
-86661002 -97696305
-97696305 -3344870
97696305 -73188922
97696305 86322845
97696305 1731050
97696305 -60730139
15513561 -97696305
65577407 97696305
...

output:

87450330.1612205
131341374.7932609
96820367.5912458
93950109.5105999
132387617.0056075
92120838.6090780
119142888.8786578
113821051.0967750
90253301.3622582
69083337.0602498
114587720.4623713
126525544.7013264
152797663.2479189
122068059.9629204
77787513.0963250
91787994.7913696
68756673.3799305
857...

result:

ok 100000 numbers

Test #79:

score: 0
Accepted
time: 215ms
memory: 7188kb

input:

100000
92376819 92376819
-92376819 92376819
92376819 -92376819
-92376819 -92376819
92376819 41805180
-11998303 92376819
21713537 92376819
-92376819 27922339
92376819 -22303293
-41355539 -92376819
76681681 -92376819
92376819 86696920
-83870485 -92376819
29507177 -92376819
92376819 -88244373
92376819 ...

output:

46201653.2820185
53697302.1358479
46190510.1874203
53399882.5071026
46785145.6808344
46286822.0141299
50856242.5705604
50476943.1091810
46604625.2676672
49322963.6448011
46334963.0629660
50388990.5052299
46473332.2713367
47623664.3778677
46223105.9963951
48689681.2982649
49121246.8071300
48014030.46...

result:

ok 100000 numbers

Test #80:

score: 0
Accepted
time: 231ms
memory: 7064kb

input:

100000
94696610 94696610
-94696610 94696610
94696610 -94696610
-94696610 -94696610
-94696610 28267614
-8921868 -94696610
-29418043 -94696610
94696610 -73710923
-94696610 86211805
94696610 -70022012
88724613 94696610
-7661772 94696610
-23421057 94696610
83791803 94696610
94696610 -44484998
83682913 -...

output:

51472469.0572600
53935198.3736315
54293248.7666910
49319138.7117181
51092308.1098875
54809448.9841402
49093868.0461603
55364458.9476689
52804371.4519340
52755587.0170129
47422455.4038970
47582660.7485897
48028514.9770173
52769981.5261909
48116130.4612036
51683895.1969703
55466875.8543795
54498674.60...

result:

ok 100000 numbers