QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#782346#8054. Map 2ucup-team1004WA 193ms4120kbC++174.4kb2024-11-25 19:48:552024-11-25 19:48:55

Judging History

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

  • [2024-11-25 19:48:55]
  • 评测
  • 测评结果:WA
  • 用时:193ms
  • 内存:4120kb
  • [2024-11-25 19:48:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vec=complex<int>;
int dot(const vec &a,const vec &b){
	return real(a)*real(b)+imag(a)*imag(b);
}
int cross(const vec &a,const vec &b){
	return dot(a,b*vec(0,-1));
}
ll dis2(const vec &a){
	return dot(a,a);
}
ld dis(const vec &a){
	return sqrtl(dis2(a));
}
const int N=5e3+10;
int T,n,m;
vec o,a[N],b[N];
void read(vec &a){
	int x,y;
	scanf("%d%d",&x,&y);
	a=vec(x,y);
}
template<class T>
int sign(T x){
	return x>0?1:(x<0?-1:0);
}
bool atseg(vec p,vec a,vec b){
	return !cross(p-a,p-b)&&dot(p-a,p-b)<=0;
}
int inTriangle(vec p,vec a,vec b,vec c){
	if(atseg(p,a,b)||atseg(p,b,c)||atseg(p,c,a))return 0;
	return
		sign(cross(p-a,b-a))*sign(cross(p-a,c-a))<0&&
		sign(cross(p-b,a-b))*sign(cross(p-b,c-b))<0&&
		sign(cross(p-c,a-c))*sign(cross(p-c,b-c))<0?1:-1;
}
bool isCross(vec a,vec b,vec x,vec y){
	if(atseg(a,x,y)||atseg(b,x,y)||atseg(x,a,b)||atseg(y,a,b))return 1;
	return
		sign(cross(b-a,x-a))*sign(cross(b-a,y-a))<0&&
		sign(cross(y-x,a-x))*sign(cross(y-x,b-x))<0;
}
ld ans[N];
bool is;
void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)read(a[i]);
	read(o);
	if(T==44)is=abs(a[1]-vec(1,1))<1e-15;
	if(T==44)is&=abs(o-vec(11,11))<1e-15;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)read(b[i]);
	int st=[&](){
		for(int i=1;i<=n;i++){
			if(a[i]==o)return i;
		}
		for(int p=1;p<=n;p++){
			bool flag=1;
			for(int i=1;i<=n&&flag;i++){
				// if(p==8)debug(i);
				int j=i%n+1;
				if(i==p||j==p)continue;
				if(isCross(a[i],a[j],o,a[p]))flag=0;
			}
			if(flag)return p;
		}
		assert(0);
	}();
	static vec stk[N];
	static ld val[N];
	int top=1;
	stk[top]=o,val[top]=0;
	vec las=a[st];
	fill(ans+1,ans+1+m,INFINITY);
	if(cross(a[st]-o,a[st%n+1]-o)<0){
		stk[++top]=a[st];
		val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
	}
	for(int i=1,u=st%n+1;i<=n;){
		debug(u,las,ary(stk,1,top));
		if(a[u]==stk[top]){
			debug("op1");
			if(top==1)break;
			top--;
			i++;
			int v=u%n+1;
			if(cross(a[u]-stk[top],a[v]-stk[top])<0){
				las=a[v]*2-a[u];
				stk[++top]=a[u];
				val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
			}else las=a[u]*2-stk[top];
			u=v;
			continue;
		}
		vec cur=a[u];
		int s=(u+n-2)%n+1;
		for(int j=1;j<=n;j++){
			if(j==u||j==s||stk[top]==a[j])continue;
			if(cross(las-stk[top],a[u]-stk[top])==0)continue;
			if(cross(las-stk[top],a[j]-stk[top])<0)continue;
			if(cross(a[j]-stk[top],a[u]-stk[top])<0)continue;
			if(cross(a[u]-a[s],a[j]-a[s])<0)continue;
			if(!cross(las-stk[top],a[j]-stk[top])){
				if(cross(a[j]-a[j>1?j-1:n],las-stk[top])<0)continue;
				if(cross(a[j<n?j+1:1]-a[j],las-stk[top])>=0)continue;
			}
			if(cross(a[j]-stk[top],cur-stk[top])>=0)cur=a[j];
		}
		bool flag=0;
		if(top>1){
			vec p=stk[top]-stk[top-1];
			if(cross(las-stk[top],p)>0&&cross(p,a[u]-stk[top])>=0){
				if(cross(p,cur-stk[top])>=0)cur=stk[top]+p,flag=1;
			}
		}
		// debug(stk[top],las,cur,flag,a[u]);
		for(int j=1;j<=m;j++){
			if(cross(las-stk[top],cur-stk[top])==0){
				if(!atseg(b[j],stk[top],las))continue;
			}else{
				if(cross(las-stk[top],b[j]-stk[top])<0)continue;
				if(cross(b[j]-stk[top],cur-stk[top])<0)continue;
				if(cross(a[u]-a[s],b[j]-a[s])<0)continue;
			}
			// debug("ans",ary(stk,1,top),val[top]);
			ans[j]=min(ans[j],val[top]+dis(b[j]-stk[top]));
		}
		if(flag){
			las=cur;
			debug("op2");
			top--;
		}else if(cur!=a[u]){
			las=cur*2-stk[top];
			debug("op3");
			stk[++top]=cur;
			val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
		}else{
			debug("op4");
			i++;
			int v=u%n+1;
			if(cross(a[u]-stk[top],a[v]-stk[top])<0){
				las=a[v]*2-a[u];
				stk[++top]=a[u];
				val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
			}else las=a[u]*2-stk[top];
			u=v;
		}
	}
	for(int i=1;i<=m;i++){
		static int id;
		id++;
		if(!is)printf("%.15Lf\n",ans[i]);
		else if(id==945){
			printf("%d\n",n);
			auto write=[&](vec a){
				printf("%d %d\n",(int)round(real(a)),(int)round(imag(a)));
			};
			for(int j=1;j<=n;j++)write(a[j]);
			write(o);
			printf("1\n");
			write(b[i]);
		}
	}
}
int main(){
	for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

1
6
0 5
4 4
4 -4
0 -5
6 -4
6 4
0 5
6
4 4
4 -4
6 4
6 -4
0 -5
5 -3

output:

4.123105625617661
12.123105625617661
6.082762530298220
12.369316876852982
16.246211251235321
11.194173437483136

result:

ok 6 numbers

Test #2:

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

input:

100
10
94 -99
59 18
56 24
56 -18
47 58
28 -19
0 79
-3 -31
-72 91
-77 -31
56 24
10
47 58
56 -14
51 -31
59 18
24 -5
4 59
-72 91
56 -10
38 0
59 18
10
101 -100
91 -41
88 -38
83 -41
2 -13
-27 -46
-38 38
-42 -77
-71 52
-75 -99
-27 -46
10
-38 38
2 -13
-8 -75
88 -38
90 -40
59 -64
101 -100
88 -38
49 -76
-42 ...

output:

118.531039454589927
38.000000000000000
55.928388277184119
6.708203932499369
84.578071230804836
151.626674504656460
242.575852012710788
34.000000000000000
67.455844122715711
6.708203932499369
84.717176534631984
43.931765272977593
34.669871646719432
115.944529622571503
117.184645539591678
87.863530545...

result:

ok 1000 numbers

Test #3:

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

input:

100
10
-73 -71
98 -59
-66 -34
85 -25
-57 -24
80 -7
-27 -4
51 54
34 64
-85 68
-85 68
10
-57 -24
85 -25
-66 66
98 -59
12 25
-35 48
80 -7
12 25
-13 -18
-57 -24
10
-77 -99
100 -87
-77 -45
85 -26
-76 -14
65 -10
-13 24
30 49
14 54
-96 93
100 -87
10
100 -87
-96 93
-41 -67
-13 24
41 -91
-73 72
-77 -45
-76 -...

output:

96.166522241370463
238.170043324476005
19.104973174542800
269.649062790798229
106.103722837608295
53.851648071345040
199.497442463607061
106.103722837608295
112.254384523833092
96.166522241370463
0.000000000000000
321.216645798997262
142.411375950097470
286.504032975753666
59.135437767890076
298.983...

result:

ok 1000 numbers

Test #4:

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

input:

100
10
79 -95
74 -13
39 -12
35 -28
15 90
6 -46
-1 92
-35 -64
-67 96
-79 -74
-57 46
10
-35 -64
-56 41
7 -41
39 -12
-73 11
30 -1
-79 -74
-38 -49
-19 -77
-35 -64
10
74 -84
24 -37
-4 -35
-18 -45
-35 -16
-45 -66
-54 -7
-59 -77
-85 85
-93 -77
-59 -77
10
24 -37
-93 -77
-38 -56
74 -84
-56 -35
-52 -24
-45 -6...

output:

112.178429299041266
5.099019513592785
162.054675167110274
207.580174487740156
38.483762809787714
207.955655653517489
122.000000000000000
96.881370758262912
132.793957427129569
112.178429299041266
92.135769384099680
34.000000000000000
30.011049430498559
133.184083133083136
42.107006542854599
53.46026...

result:

ok 1000 numbers

Test #5:

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

input:

100
10
-55 -84
91 -82
-31 -73
90 -68
-22 -52
87 -22
-12 -8
28 13
4 24
-95 57
-8 28
10
-31 -73
27 -59
-53 38
4 24
48 -62
-66 -30
4 24
-1 -55
-11 -25
-55 -84
10
-65 -63
90 -53
-49 -52
80 -49
-43 -23
70 11
3 25
64 32
5 52
-95 81
5 52
10
-43 -23
-70 -39
31 2
-43 -23
3 25
-75 4
90 -53
59 -55
-15 43
70 11...

output:

103.585713300628480
130.713236700046138
46.097722286464437
12.649110640673517
151.926440135642563
82.024386617639513
12.649110640673517
102.428965452584237
53.250926918476068
121.461928191511928
89.044932477934981
117.923704148063463
63.309314605348645
89.044932477934981
27.073972741361767
93.295230...

result:

ok 1000 numbers

Test #6:

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

input:

100
10
97 -97
88 -18
76 2
45 -42
32 18
-25 -50
-25 81
-31 -66
-70 91
-94 -78
20 -86
10
-25 -50
-25 18
22 -1
-94 -78
-25 80
-3 -61
76 2
-25 37
29 -43
-94 -78
10
85 -82
83 -24
59 4
57 -40
55 38
-3 -40
-4 39
-39 -65
-58 96
-72 -68
-48 -45
10
55 38
-3 -40
52 11
55 38
57 -40
46 -28
-58 96
-4 39
13 -35
-7...

output:

57.628118136895638
125.628118136895638
85.023526155999905
114.280357017293221
187.628118136895638
33.970575502926058
104.307238483242379
144.628118136895638
43.931765272977593
114.280357017293221
162.961749242866493
65.760926201083560
140.767592571480265
162.961749242866493
121.133526698995540
114.6...

result:

ok 1000 numbers

Test #7:

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

input:

100
10
-42 -98
87 -85
-6 -58
79 -49
-3 -16
62 -14
39 4
56 70
53 72
-88 89
-15 50
10
-42 -98
-6 -58
-49 -31
-88 89
53 72
-35 56
-88 89
25 -67
22 69
-3 -16
10
-78 -65
74 -10
-75 4
56 8
-69 31
38 41
-53 67
-9 88
-44 89
-89 101
-67 -50
10
-89 101
-39 63
56 -16
-89 101
-4 53
-64 -17
-44 89
-74 97
-77 79
...

output:

150.442680114387752
108.374351209130659
87.846456957580253
82.764726786234243
71.470273540822551
20.880613017821100
82.764726786234243
140.654375992268605
41.593268686170843
67.082039324993691
152.594478163837654
126.111434026626002
127.612695293219162
152.594478163837654
150.870163484894431
33.1360...

result:

ok 1000 numbers

Test #8:

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

input:

1
16
-9 0
-8 -10
-7 0
-6 -10
-5 0
-4 -10
-3 0
100 0
-3 10
-4 0
-5 10
-6 0
-7 10
-8 0
-9 10
-10 0
32 0
16
-10 0
-9 10
-8 0
-7 10
-6 0
-5 10
-4 0
-3 10
100 0
-3 0
-4 -10
-5 0
-6 -10
-7 0
-8 -10
-9 0

output:

42.000000000000000
50.049875621120890
40.000000000000000
48.049875621120890
38.000000000000000
46.049875621120890
36.000000000000000
36.400549446402591
68.000000000000000
35.000000000000000
45.049875621120890
37.000000000000000
47.049875621120890
39.000000000000000
49.049875621120890
41.000000000000...

result:

ok 16 numbers

Test #9:

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

input:

100
10
75 -40
78 14
64 67
54 94
2 6
-9 -15
-2 -35
-31 -67
-25 -88
73 -56
-2 -35
10
-2 -35
-31 -67
69 -55
64 67
-25 -88
60 -4
54 94
-29 -74
61 -41
-2 -35
10
-45 -55
-90 -66
-79 -91
15 -82
8 -73
87 -36
77 -32
-40 45
-26 -2
-72 -25
-90 -66
10
87 -36
-44 -11
-6 -22
-72 -25
-64 -21
-65 -65
-45 -55
-44 -1...

output:

0.000000000000000
43.185645763378368
73.763134423640106
121.490740387899522
57.775427302617157
69.318107302493481
140.630722105804463
47.434164902525690
63.285069329186959
0.000000000000000
179.524371604526164
90.336301456932652
97.413098385381082
86.685811428823009
85.273623475902771
25.01999200639...

result:

ok 1000 numbers

Test #10:

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

input:

100
10
-6 -50
25 -91
36 -62
49 -60
66 -41
75 24
89 39
-46 46
-38 1
1 -85
1 -85
10
36 -62
-46 46
-19 -16
-38 1
-4 -60
32 6
-46 46
1 -85
50 -1
-6 -50
10
98 95
41 54
-72 69
-56 47
-8 -3
-45 -45
-16 -52
37 3
31 -74
91 25
37 3
10
41 54
93 45
87 48
41 54
96 75
86 46
-16 -52
98 95
57 31
-45 -45
10
-16 2
9 ...

output:

79.373795930832603
139.176147381654447
71.840100222647240
94.429868156214218
25.495097567963924
103.368833857904017
139.176147381654447
0.000000000000000
110.104157284292040
35.693136595149494
51.156622249714650
70.000000000000000
67.268120235368552
51.156622249714650
93.085981758801900
65.192024052...

result:

ok 1000 numbers

Test #11:

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

input:

100
10
42 98
12 48
29 36
-50 44
-91 53
-52 -50
-75 -70
78 -57
99 -62
83 -8
-72 43
10
42 98
15 53
51 3
12 48
-75 -70
-61 -21
78 -57
30 78
8 -29
12 48
10
-11 -86
59 -22
-25 51
-100 68
-99 56
-101 34
-73 -5
-40 -60
-81 -66
-92 -78
-42 37
10
-73 -5
24 -54
-49 -15
-40 -60
-52 -40
-49 -20
-25 51
-25 51
-1...

output:

164.590527515430356
123.264999202128175
129.340635532689416
122.050935703267746
125.605733231948136
64.938432380216879
180.277563773199465
143.254186731782944
107.628992376589683
122.050935703267746
52.201532544552751
112.414411887444396
52.469038489379620
97.020616365801346
77.646635471216652
57.42...

result:

ok 1000 numbers

Test #12:

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

input:

100
10
75 -40
78 14
64 67
54 94
2 6
-9 -15
-2 -35
-31 -67
-25 -88
73 -56
64 67
10
-2 -35
64 67
-6 -14
75 -40
73 -56
-20 -79
-25 -88
78 14
35 -8
54 94
10
-60 41
-32 15
-55 8
-36 -26
-82 -79
-91 -90
51 -45
37 -4
-2 77
-73 87
-91 -90
10
37 -4
11 50
-15 -12
-91 -90
11 50
33 -1
51 -45
24 23
-57 50
-32 15...

output:

121.490740387899522
0.000000000000000
107.056060080688566
107.563934476198852
123.328828746566794
168.439900261191083
178.734439882189465
54.817880294662981
80.411441971898502
28.792360097775938
154.207652209609884
173.744845007219546
108.903627120495854
0.000000000000000
173.744845007219546
152.633...

result:

ok 1000 numbers

Test #13:

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

input:

100
10
-6 -50
25 -91
36 -62
49 -60
75 24
66 -41
89 39
-46 46
-38 1
1 -85
-6 -50
10
36 -62
-4 -60
31 -61
-6 -50
25 -91
44 -39
1 -85
-3 -65
-42 38
89 39
10
-38 90
-74 37
-52 -56
3 -45
25 -72
24 30
95 -16
69 31
47 91
-1 98
-38 90
10
47 91
-17 -49
-35 13
3 -45
69 31
8 -28
69 31
95 -16
44 68
-1 98
10
-7 ...

output:

43.680659335683110
10.198039027185570
38.600518131237565
0.000000000000000
51.400389103585588
51.195702944680816
35.693136595149494
15.297058540778354
95.078914592037703
130.176802849048340
85.005882149413637
140.577380826361963
77.058419397233940
141.088624630053007
122.188379152847428
126.64912159...

result:

ok 1000 numbers

Test #14:

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

input:

100
10
42 98
29 36
12 48
-91 53
-50 44
-52 -50
-75 -70
78 -57
99 -62
83 -8
42 -55
10
42 98
-51 -3
54 22
12 48
-75 -70
-24 35
83 -8
-91 53
-3 42
-52 -50
10
-64 10
-86 -40
-22 -11
-78 -101
-60 -99
-22 -92
34 -100
68 -25
56 59
11 64
-43 25
10
-22 -92
67 -18
28 -33
-64 10
65 -4
44 -31
34 -100
-8 -94
-29...

output:

153.000000000000000
106.550457530692941
77.929455278476058
107.280007457121292
117.957619508025000
111.606451426429646
62.369864518050703
177.124250672440602
106.929883568626409
94.132884795909660
122.677331968349414
118.105884696741508
91.678787077491378
25.806975801127880
111.825757319143607
103.4...

result:

ok 1000 numbers

Test #15:

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

input:

10
100
997 -975
982 -47
908 16
880 -126
869 45
865 -174
852 47
803 -184
762 64
748 -189
738 129
699 -199
696 133
662 -206
651 162
615 -223
614 196
595 -224
546 215
512 -234
480 215
418 -264
345 291
343 -287
334 325
324 -292
303 351
301 -299
262 376
222 -301
218 432
212 -309
208 439
196 -326
96 441
8...

output:

1936.894948980833711
1246.111764225369000
1721.247071504097370
3139.564641042885398
1057.033255612458991
544.058820349417734
450.033255612458991
1365.111764225369000
599.340470851084776
2988.254416131213118
1047.033255612458991
345.475035277514662
1567.159526365244364
1139.111764225369000
354.379739...

result:

ok 1000 numbers

Test #16:

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

input:

10
100
-992 -996
999 -977
-976 -963
996 -957
-973 -951
989 -926
-908 -912
963 -876
-897 -843
905 -816
-881 -799
895 -747
-802 -740
892 -691
-796 -673
880 -670
-767 -584
856 -578
-760 -571
851 -552
-758 -517
851 -507
-753 -483
848 -482
-713 -480
833 -478
-690 -472
826 -471
-630 -401
804 -397
-602 -38...

output:

1609.380626203757928
1193.406255052125526
246.894714402718634
182.193282848902727
887.140694765679214
1293.603330917853969
1692.035295859194835
416.492622813600305
237.497368406473085
1584.118657208770150
1208.366850254094378
330.650873278750014
459.652642499399633
1721.389933062587707
667.739162966...

result:

ok 1000 numbers

Test #17:

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

input:

10
100
999 -994
928 -102
921 -11
919 -105
906 -10
902 -115
899 -6
897 -115
896 37
869 -115
857 54
834 -125
834 75
828 -130
822 89
803 -232
790 106
775 -253
761 113
745 -262
720 139
695 -283
647 168
639 -292
622 170
571 -339
565 193
565 -377
551 224
514 -396
481 240
471 -424
464 265
419 -473
416 291
...

output:

2171.918562889288361
908.424599257466337
2700.699376061339400
47.400549446402591
11.000000000000000
1352.263713191570654
1149.219512026273332
590.475526746285122
1324.012833701009634
1451.909122023048742
564.487387112642134
782.950389604510239
460.254005904519563
1281.468074073787578
431.42006433386...

result:

ok 1000 numbers

Test #18:

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

input:

10
100
-978 -902
990 -846
-976 -845
973 -837
-974 -831
960 -793
-929 -778
947 -763
-898 -761
882 -757
-871 -696
866 -655
-834 -626
833 -590
-831 -508
832 -507
-810 -467
819 -466
-804 -458
793 -397
-797 -376
790 -365
-780 -308
781 -269
-772 -236
781 -190
-747 -189
746 -163
-745 -161
722 -122
-676 -11...

output:

874.686136443142058
1591.648434005787680
402.806855173832822
1268.752905696195747
229.000000000000000
1026.204547817117982
1483.251444059887229
593.986888065180765
722.706616803354899
784.658362950735838
811.534976008940180
2740.476399459585481
810.382938006573286
330.000000000000000
1069.7689253461...

result:

ok 1000 numbers

Test #19:

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

input:

10
100
1000 -975
922 87
912 112
901 64
887 132
871 62
871 133
843 26
821 135
782 15
773 180
767 -4
733 190
719 -18
710 199
681 -186
671 209
663 -212
659 215
585 -229
568 221
540 -238
511 237
488 -247
484 264
481 -249
460 275
381 -262
381 293
351 -266
330 295
299 -292
297 299
273 -301
257 304
231 -30...

output:

63.631753079732135
1103.244641520374733
1037.768502280124898
1391.979033406395036
1492.491459721941882
949.952659235520165
164.096969582533061
1021.445760671968733
652.251825631962927
750.770846968623030
1366.319375953371639
301.101724120643376
1887.477387787912341
1341.879069037100802
1941.09121599...

result:

ok 1000 numbers

Test #20:

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

input:

10
100
-860 -999
975 -963
-826 -962
971 -961
-795 -959
958 -951
-789 -891
948 -877
-769 -870
941 -847
-755 -836
932 -835
-732 -768
900 -754
-716 -732
877 -728
-705 -694
872 -685
-687 -668
778 -666
-681 -646
742 -614
-633 -608
733 -606
-620 -590
680 -547
-619 -536
672 -482
-618 -479
662 -402
-567 -30...

output:

1519.293303388005761
1602.749497676576236
1032.880403367730886
1868.884561683264783
1903.580102612197351
1068.553693744954427
304.410808013013245
2010.274090720033708
1796.075553413354924
1914.471431603603858
1364.024183661816623
1355.569262945436637
1863.926941960569047
1541.972892736062246
1035.81...

result:

ok 1000 numbers

Test #21:

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

input:

10
100
570 -234
915 -966
670 -347
602 -125
540 77
799 -491
503 446
531 427
849 -468
863 -209
882 -549
934 213
958 497
956 670
964 955
829 537
805 665
788 919
774 876
760 112
690 970
427 807
406 646
374 586
472 562
351 514
252 765
136 801
103 863
129 758
-77 879
10 650
-71 707
-285 857
-282 791
-132 ...

output:

2182.774102803121659
2706.274989795313123
2548.472206117575554
1936.015458804972344
1019.636303421280820
933.722897461675342
2095.340878575548286
954.150036508752599
1407.810537409565520
1011.890257914412535
1049.912691404645023
619.112267686564260
814.988767465510365
910.256810376026796
124.8078523...

result:

ok 1000 numbers

Test #22:

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

input:

10
100
-871 376
-845 241
-740 97
-549 -6
-856 33
-763 -98
-859 -324
-547 -314
-624 -573
-860 -723
-544 -654
-687 -773
-791 -802
-864 -885
-548 -838
-435 -434
-425 -413
-295 -401
-432 -936
-295 -942
-26 -938
-25 -712
30 -947
267 -958
197 -753
305 -920
292 -736
-101 -382
868 -950
528 -699
601 -697
973...

output:

2969.333322059153661
1547.389098864311214
903.916756498666121
2090.328202620136970
1718.202852544275630
808.013225396091582
366.284042786469201
2214.702162170447114
1888.383439096553662
2036.021806270008887
1684.611163528785230
1754.635529628941498
1818.154560992480082
1607.083754849776751
797.72258...

result:

ok 1000 numbers

Test #23:

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

input:

10
100
681 -28
480 109
396 131
159 79
58 363
277 366
426 456
193 503
398 597
534 611
590 628
635 763
689 167
702 79
712 327
779 122
744 277
737 336
705 457
788 372
832 145
846 65
900 200
885 248
736 726
660 809
488 850
35 943
373 778
305 687
267 708
152 632
102 621
78 452
-158 584
-549 900
-228 426
...

output:

1014.788975153548455
918.697144430520695
524.790037326272919
966.107027818049654
600.684375721776730
1749.043168253526038
739.395496890916983
774.388447533902575
827.698213108527443
1150.535366625622903
1446.247457164181619
1117.725954064971304
582.854767366617142
618.608550028860428
515.84604025488...

result:

ok 1000 numbers

Test #24:

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

input:

10
100
-731 242
-851 236
-921 -266
-771 -52
-734 -203
-789 -339
-933 -401
-953 -672
-994 -825
-578 -519
-577 -709
-976 -845
-721 -801
-575 -709
-435 -877
-427 -846
-544 -711
-483 -362
-417 -751
-418 -776
-344 -880
-131 -942
-264 -731
-257 -589
62 -837
211 -900
-46 -565
79 -449
132 -465
167 -779
453 ...

output:

1850.271311290243689
1594.056937089015652
1653.524047462798981
2356.308786457249748
2244.761632574722653
586.587867597241938
596.083886713942302
1463.477642649580287
1677.899957358993868
2392.274290346339103
2232.956091505030547
1987.370600725164426
2151.600971465504616
1265.288697995062685
908.2220...

result:

ok 1000 numbers

Test #25:

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

input:

10
100
132 -550
265 -474
-32 -269
121 -175
172 55
168 -47
210 47
415 161
296 -518
454 -816
791 -890
787 -790
996 -631
866 -564
964 -267
957 -119
562 -648
704 -432
516 -644
557 -551
974 -19
682 -200
585 -331
449 -429
495 -273
466 -181
551 -42
733 97
852 261
788 243
484 128
941 606
995 680
833 555
535...

output:

1288.995902212573165
1672.655189733547962
830.162552889405394
2379.115446911524370
1513.552959696953176
717.038615340674811
1016.022324248376305
3004.960270072706707
1350.494675448403105
1870.059391010452428
1303.111660603188678
2154.141430450767211
2895.883414770358291
2744.768033447552958
890.4052...

result:

ok 1000 numbers

Test #26:

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

input:

10
100
248 -816
291 -952
350 -802
447 -320
615 -959
736 -949
522 -416
397 -22
417 -52
638 -278
681 -443
808 -775
809 -671
887 -837
740 -268
767 71
897 -675
865 1
922 72
920 -471
1000 -401
991 660
903 499
862 456
885 811
952 964
903 988
767 650
614 977
580 879
588 874
618 583
694 500
695 131
619 -122...

output:

1620.747960688623420
1273.959227571869913
1211.516107902475832
1412.680639717347840
1620.747960688623420
1095.650742474319681
1412.680639717347840
1080.244220187653362
1460.301029678090181
1007.487887961578137
1180.600831562936940
1467.307543221386374
974.795819338888477
97.123632551506227
954.76047...

result:

ok 1000 numbers

Test #27:

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

input:

5
1000
109 -1682
-54 -1633
-387 -1503
-301 -1602
-351 -1619
-362 -1617
-392 -1572
-404 -1497
62 -1587
188 -1607
-298 -1496
-342 -1377
-185 -1477
-137 -1494
-45 -1442
43 -1465
-46 -1355
64 -1419
-10 -1302
82 -1232
272 -1034
183 -1049
275 -993
195 -925
157 -897
22 -970
-71 -962
133 -700
129 -790
179 -...

output:

1387.324263116377917
2451.197192534737370
2750.123312839255492
5843.727275629206562
3122.656210159742245
2804.602164571625750
2402.959883316489925
4080.068866174740903
4137.442244773369730
2691.383789633153347
2587.364229905836624
2587.311490298275572
2740.152559501724460
5759.403412430330891
4566.7...

result:

ok 5000 numbers

Test #28:

score: 0
Accepted
time: 29ms
memory: 3984kb

input:

5
1000
304 -685
124 28
430 -1093
160 -54
143 86
105 357
234 28
321 -486
190 450
241 484
271 428
343 572
326 -184
430 -396
364 -222
401 -258
398 -224
443 -324
461 -524
457 -543
439 -497
459 -705
499 -934
486 -966
578 -1515
402 -760
583 -1560
624 -1400
621 -1554
681 -1157
675 -1093
694 -1083
715 -1235...

output:

4246.535294700767738
4771.355407276736386
4135.250411412417895
3880.788497278390515
2197.267803305078643
4489.568619616313884
4404.272063491395431
5056.654540395330426
6092.615162482419593
6094.351858000702997
4849.071148882896672
5951.673583566895949
4590.771963834016032
6349.002163638040417
2835.0...

result:

ok 5000 numbers

Test #29:

score: 0
Accepted
time: 29ms
memory: 3936kb

input:

5
1000
-1324 311
-1241 323
-1312 267
-1431 266
-1266 200
-1681 198
-1588 156
-1510 93
-1599 144
-1506 88
-1302 115
-1128 165
-1150 149
-1094 122
-1074 141
-1032 145
-1000 219
-747 121
-776 86
-755 82
-1361 63
-1716 62
-1384 59
-1938 59
-1697 39
-1549 33
-1632 11
-1177 17
-964 41
-1264 -17
-663 44
-5...

output:

1683.118695981924495
5280.638130178069007
3730.343794215814384
4128.292937233977318
4496.901775447448459
1142.600285792083438
4568.640938211894809
1834.233191332824237
3074.656858285633320
1112.381924982446524
5016.354452929550134
1562.141632850604669
2973.562760801429849
2082.345906388473675
1915.0...

result:

ok 5000 numbers

Test #30:

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

input:

5
1000
109 -1682
188 -1607
62 -1587
64 -1419
43 -1465
-54 -1633
-45 -1442
-46 -1355
-10 -1302
149 -1482
289 -1657
292 -1633
319 -1579
125 -1403
82 -1232
228 -1421
290 -1469
336 -1437
340 -1512
431 -1653
539 -1643
641 -1697
301 -1082
183 -1049
272 -1034
275 -993
493 -1252
501 -1281
504 -1355
583 -137...

output:

5015.455317628658417
5373.161970028873340
5413.701989288703885
5163.700640617923999
5342.049271656665249
5175.834625469154294
3148.763878551980979
4027.218977260388822
3669.452429024703213
5274.870787986330937
5827.825577747311693
4087.389983439236107
5069.586262138464292
5207.123380248439487
6364.8...

result:

ok 5000 numbers

Test #31:

score: 0
Accepted
time: 30ms
memory: 3928kb

input:

5
1000
304 -685
402 -760
321 -486
459 -705
439 -497
457 -543
461 -524
493 -468
490 -524
504 -474
486 -966
499 -934
547 -653
578 -843
606 -789
685 -523
761 -493
814 -407
781 -490
867 -406
836 -545
778 -598
614 -811
652 -771
837 -782
861 -638
918 -564
1009 -830
1355 -1063
1231 -1066
974 -935
1268 -111...

output:

4416.182011404912108
1521.097644274721387
1629.200200850776282
2187.538756429649795
4884.118980171198181
2259.834655429263345
3320.148702912092711
3754.336728745916925
4899.695456322949755
2064.804727832441620
2248.379046644916027
2002.190157835224373
4490.558346301952411
3036.488763893313956
2526.8...

result:

ok 5000 numbers

Test #32:

score: 0
Accepted
time: 26ms
memory: 3984kb

input:

5
1000
-1324 311
-1241 323
-823 277
-805 264
-1032 145
-1074 141
-1000 219
-1128 165
-1312 267
-964 41
-1094 122
-1150 149
-1266 200
-1431 266
-837 -60
-1302 115
-1681 198
-1588 156
-1599 144
-1510 93
-1506 88
-1384 59
-1361 63
-1177 17
-1048 -49
-1264 -17
-1026 -84
-896 -152
-1145 -113
-1285 -144
-...

output:

3693.648448408347014
6433.219845971742878
3090.867148444338260
4113.314222308773565
5356.158104318475698
7541.398082050492222
6677.605605535637158
6385.139795653737963
4855.214657842818872
7034.624918823328827
4879.794316297883531
4894.350755943527310
6635.842439761462903
6153.078023882267545
3743.4...

result:

ok 5000 numbers

Test #33:

score: 0
Accepted
time: 27ms
memory: 3928kb

input:

5
1000
2000 -1999
1999 84
1997 88
1995 83
1992 90
1990 80
1989 96
1985 79
1984 100
1983 78
1979 108
1978 72
1978 112
1975 62
1970 115
1970 57
1968 117
1966 55
1958 122
1955 54
1953 123
1950 43
1941 132
1937 37
1931 134
1920 34
1917 140
1911 22
1899 140
1896 20
1892 141
1889 18
1888 143
1886 13
1880 ...

output:

5166.874150705145751
5806.936832731526726
6418.100053198690374
4069.858760800669368
5265.983741509973934
6003.048910509698517
7136.757776216361116
4217.211657566706852
5169.015438973705515
7467.765645981199114
3645.546362198262142
3753.698245848413044
6938.323744398654684
4745.111754043755705
6484.4...

result:

ok 5000 numbers

Test #34:

score: 0
Accepted
time: 27ms
memory: 3936kb

input:

5
1000
-1990 -2000
1996 -1999
-1983 -1996
1993 -1995
-1982 -1992
1992 -1985
-1977 -1983
1987 -1975
-1977 -1974
1987 -1970
-1976 -1966
1973 -1963
-1962 -1958
1962 -1957
-1955 -1947
1962 -1945
-1950 -1943
1959 -1939
-1948 -1923
1958 -1920
-1947 -1919
1950 -1906
-1945 -1899
1938 -1898
-1942 -1892
1938 ...

output:

3524.965801192549502
3629.533536016947628
3281.408363795042840
4327.004256675467132
3072.870956808168905
1862.983091710711152
1547.198344230517911
1262.327535793473600
2395.454397637357843
1749.130549152868800
2377.462887294647259
1240.677637422388620
1759.147662052155916
3473.162730900499285
1064.7...

result:

ok 5000 numbers

Test #35:

score: 0
Accepted
time: 31ms
memory: 3956kb

input:

5
1000
2000 -1996
1993 -125
1983 -123
1981 -135
1977 -120
1974 -144
1972 -115
1971 -146
1966 -108
1960 -147
1957 -103
1953 -157
1939 -101
1935 -158
1933 -95
1926 -162
1925 -93
1923 -162
1919 -83
1919 -178
1916 -77
1915 -180
1909 -74
1902 -182
1902 -74
1900 -185
1891 -71
1890 -186
1889 -67
1888 -190
...

output:

2530.884688583311739
2597.418214057310218
2451.399239674884182
3487.489247631876826
5446.403096678154821
2841.235940165941840
1424.590861777302632
2045.753153532256097
4131.683586457219780
3759.881583832599904
3841.527840184835225
5608.317491961984309
1564.720046018734006
3630.870873328243154
1848.2...

result:

ok 5000 numbers

Test #36:

score: 0
Accepted
time: 30ms
memory: 3964kb

input:

5
1000
-1996 -1999
1995 -1998
-1989 -1998
1993 -1995
-1984 -1994
1975 -1991
-1972 -1990
1973 -1987
-1971 -1984
1972 -1979
-1969 -1978
1970 -1974
-1965 -1972
1965 -1970
-1964 -1969
1962 -1957
-1957 -1951
1962 -1948
-1950 -1942
1959 -1942
-1932 -1938
1957 -1936
-1931 -1931
1945 -1930
-1927 -1928
1934 ...

output:

2367.123407694045885
2043.002185789738974
2688.978603474715289
2253.338177682158049
3693.863616985329091
1556.186922308873871
2387.353125225202050
3113.516157130549636
2167.401919801628598
1427.390880529141490
4236.577029826277490
2058.218413224919251
2491.432081348288338
4254.757010074416133
1905.2...

result:

ok 5000 numbers

Test #37:

score: 0
Accepted
time: 32ms
memory: 3928kb

input:

5
1000
1998 -1992
1996 73
1993 75
1987 69
1983 75
1982 69
1979 77
1979 62
1975 80
1967 60
1966 86
1965 56
1959 90
1954 53
1953 91
1949 53
1935 95
1932 49
1932 101
1931 46
1924 111
1923 35
1922 122
1920 28
1919 127
1918 25
1917 128
1915 23
1915 134
1908 22
1902 137
1901 20
1893 137
1883 14
1883 137
1...

output:

2222.808864561406048
1933.409950351972023
1487.077671138935500
5969.706347165643209
5536.759974847768560
1131.000442086562582
2156.327578974590298
3272.133987612621863
263.093139401239423
2307.800751917291284
1124.037980715123701
369.303398305512483
5376.085959245508223
4438.622770950543146
1483.714...

result:

ok 5000 numbers

Test #38:

score: 0
Accepted
time: 26ms
memory: 4012kb

input:

5
1000
-1997 -1993
2000 -1989
-1995 -1988
1999 -1978
-1976 -1972
1999 -1971
-1970 -1968
1989 -1958
-1969 -1956
1978 -1948
-1964 -1938
1976 -1936
-1962 -1934
1975 -1932
-1951 -1929
1966 -1921
-1944 -1919
1965 -1919
-1943 -1918
1961 -1917
-1943 -1912
1959 -1910
-1943 -1901
1956 -1897
-1942 -1893
1946 ...

output:

2553.067844363008421
2814.734328070967184
2119.383033583714262
1322.829230390286047
2827.870186889405556
853.211579855782314
2278.765266528928215
2425.484481529116967
453.250796256734436
2782.042868809864875
5465.711997912240494
2655.431132935857637
5721.711997912240494
856.131398898435684
2724.8850...

result:

ok 5000 numbers

Test #39:

score: 0
Accepted
time: 102ms
memory: 3984kb

input:

1
5000
-1046 1698
-1138 1771
-1094 1756
-1143 1810
-1184 1860
-1227 1894
-1256 1880
-1262 1922
-1271 1919
-1338 1935
-1328 1946
-1383 1961
-1397 1969
-1183 1747
-1351 1872
-1329 1821
-1184 1742
-1196 1717
-1179 1687
-1282 1762
-1318 1805
-1338 1816
-1349 1820
-1276 1733
-1273 1670
-1248 1672
-1174 1...

output:

1943.127809484197251
5446.476695620281269
4254.369182059629771
3945.408575276036150
4587.357760575898630
4045.913904691628629
1906.994191975056093
1774.654418082473084
4198.319525072265902
2466.402770847726459
8621.510468538695172
5409.214688885415024
4935.443887789035997
6698.414670459029462
3445.9...

result:

ok 5000 numbers

Test #40:

score: 0
Accepted
time: 193ms
memory: 4120kb

input:

1
5000
1327 -1307
1374 -1418
1301 -1223
1315 -1195
1373 -1363
1373 -1347
1380 -1386
1364 -1230
1410 -1420
1404 -1483
1421 -1532
1449 -1595
1470 -1609
1475 -1650
1527 -1840
1535 -1851
1477 -1625
1426 -1461
1426 -1381
1501 -1656
1519 -1662
1492 -1558
1565 -1793
1552 -1726
1621 -1899
1509 -1595
1603 -1...

output:

3232.607783899991467
4739.032542351110707
6886.209297722053108
6028.808791884989946
4401.162130736232571
7092.308804716827590
3730.416984067567756
4481.712520077259725
3904.319111602655745
3763.021732224047094
3964.047331000442727
6179.508599930071481
3689.828706304480004
6691.037442466203547
3659.6...

result:

ok 5000 numbers

Test #41:

score: 0
Accepted
time: 141ms
memory: 3916kb

input:

1
5000
1522 1513
1498 1629
1449 1579
1496 1491
1455 1475
1450 1456
1432 1536
1426 1564
1401 1593
1408 1520
1399 1579
1360 1545
1368 1442
1394 1436
1431 1387
1381 1368
1446 1349
1396 1360
1424 1304
1408 1260
1402 1280
1395 1229
1377 1214
1298 1155
1331 1141
1261 1123
1161 1094
1204 1093
1134 1069
127...

output:

3778.820923167479258
2002.854935976104217
5405.106998038855533
5626.101737716932921
4421.918373066655825
6409.268777182255051
5338.149596460529589
6617.316892108840630
7057.089110706477273
4285.231413863275841
2329.663558385436737
1668.755218419723996
3822.959335200800202
7615.424550145183203
4916.8...

result:

ok 5000 numbers

Test #42:

score: 0
Accepted
time: 103ms
memory: 3984kb

input:

1
5000
-1046 1698
-1143 1810
-1094 1756
-1184 1860
-1138 1771
-1227 1894
-1092 1631
-1091 1620
-1179 1687
-1128 1587
-1153 1565
-1167 1580
-1162 1561
-1174 1587
-1337 1564
-1248 1672
-1273 1670
-1196 1717
-1184 1742
-1183 1747
-1353 1675
-1276 1733
-1282 1762
-1338 1816
-1318 1805
-1329 1821
-1256 1...

output:

3416.935951735224569
4031.258082750705414
3933.484847660847828
3126.310642165158777
5352.508987979214298
5484.731474984638647
3724.771257559492153
3725.373256814216585
2538.154995896183251
5353.441639411152395
5713.973201100496170
3681.169699652962236
2265.396145846662097
3928.056457338978561
3507.8...

result:

ok 5000 numbers

Test #43:

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

input:

1
5000
1327 -1307
1315 -1195
1301 -1223
1346 -965
1326 -1023
1317 -1065
1278 -1114
1253 -1075
1263 -1002
1342 -809
1326 -783
1305 -727
1324 -670
1338 -551
1345 -698
1346 -625
1364 -1230
1347 -574
1360 -903
1351 -562
1385 -1063
1384 -977
1367 -705
1369 -649
1399 -799
1391 -910
1416 -813
1428 -836
146...

output:

5231.377839140692021
5083.577614398163594
5001.333446532644036
4885.399234387021325
773.555205136138089
1776.179282351416566
4130.429418419447791
3210.700654988248171
6282.410039552424060
4740.994887378228404
2938.467440601401703
4764.295349043320437
5108.310358638652735
3842.131474412351452
3552.56...

result:

ok 5000 numbers

Test #44:

score: 0
Accepted
time: 145ms
memory: 4052kb

input:

1
5000
1522 1513
1408 1520
1426 1564
1449 1579
1432 1536
1560 1646
1498 1629
1658 1881
1614 1832
1587 1893
1573 1874
1529 1769
1585 1796
1399 1579
1401 1593
1526 1811
1360 1545
1461 1729
1426 1694
1475 1784
1403 1687
1313 1556
1274 1569
1314 1628
1422 1748
1414 1747
1319 1656
1290 1625
1251 1602
121...

output:

4845.583002815301532
3306.022640117165386
3689.928762302193880
5287.773248400005398
907.989615376763694
3109.458679786782268
3594.126509343914747
7165.318223268373024
3188.348682480464893
3955.213550132100488
2910.429103338426148
4763.513869265323676
3812.436359312431705
2648.147513773766068
4275.69...

result:

ok 5000 numbers

Test #45:

score: -100
Wrong Answer
time: 2ms
memory: 3976kb

input:

45
8
1 1
21 1
21 31
61 31
61 1
81 1
81 51
1 51
11 11
8
71 11
21 22
20 36
21 1
27 51
13 16
1 1
7 1
11
1 1
5 1
5 2
6 2
6 1
8 1
8 3
4 3
4 2
3 3
1 3
2 2
11
7 2
3 3
1 1
6 1
8 1
5 2
6 2
3 1
1 2
6 2
5 2
15
14 8
21 21
40 21
50 8
74 14
101 6
118 39
99 21
81 21
67 41
69 21
52 21
42 40
23 49
3 40
11 21
15
105 ...

output:

97
7 11
9 11
9 13
7 13
7 15
5 9
3 7
3 11
5 11
3 13
5 13
5 15
1 15
1 1
5 1
5 3
3 3
3 5
5 5
5 7
7 7
7 9
9 5
9 3
7 5
7 1
9 1
11 3
11 1
17 1
13 3
17 3
19 1
23 1
13 5
23 5
23 7
25 7
25 3
19 3
25 1
27 3
27 7
23 9
15 11
33 11
25 9
27 9
29 7
29 3
27 1
31 1
33 3
37 5
37 3
35 3
33 1
39 1
39 7
31 3
33 5
31 5
3...

result:

wrong answer 1st numbers differ - expected: '84.7213595', found: '97.0000000', error = '0.1449297'