QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187416#3854. Radarballance#AC ✓153ms5764kbC++171.8kb2023-09-24 17:06:132023-09-24 17:06:13

Judging History

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

  • [2023-09-24 17:06:13]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:5764kb
  • [2023-09-24 17:06:13]
  • 提交

answer

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld PI = 2*acos(ld(0));
ld angle(ld x, ld y)
{
	if (x == 0)
	{
		if (y > 0)
			return PI / 2;
		return -PI / 2;
	}
	if (x > 0)
		return atan(ld(y) / x);
	else
		if (y < 0)return -PI + atan(ld(y) / x);
		else
			return PI + atan(ld(y) / x);
}
ld len(ld x, ld y)
{
	return sqrt(x * x + y * y);
}
const int N = 100010;

int r[N];
ld a[N];
ld len2(ld alpha, ld r, ld x, ld y)
{
	ld dx = r * cos(alpha), dy = r * sin(alpha);
	return len(dx - x, dy - y);
}
signed main()
{
	//cout << PI;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int rr, ff, tt;
	cin >> rr >> ff >> tt;
	for (int i = 1; i <= rr; i++)
		cin >> r[i];
	sort(r + 1, r + rr + 1);
	r[0] = -1e8;
	r[rr + 1] = 1e8;
	for (int i = 1; i <= ff; i++)
	{
		int x, y; cin >> x >> y;
		a[i] = angle(x, y);
		//cout << x << ' ' << y << ' ' << a[i] << '\n';
	}
	sort(a + 1, a + ff + 1);
	a[ff + 1] = a[1] + 2 * PI;
	a[0] = a[ff] - 2 * PI;
	while (tt--)
	{
		int x, y; cin >> x >> y;
		ld leng = len(x, y);
		/*int l = lower_bound(r, r + rr + 2, leng) - r;
		int s[3];
		s[1] = r[l - 1], s[2] = r[l];*/
		ld alpha = angle(x, y);
		int l = lower_bound(a + 1, a + ff + 2, alpha) - a;
		ld p[3];
		p[1] = a[l - 1], p[2] = a[l];
		ld ans = 1e10;
		for (int i = 1; i <= 2; i++)
		{
			ld beta = p[i];
			ld shadowlen = leng * cos(beta - alpha);
			int l = lower_bound(r, r + rr + 2, shadowlen) - r;
			int s[3];
			s[1] = r[l - 1], s[2] = r[l];
			for (int j = 1; j <= 2; j++)
				ans = min(ans, len2(beta, s[j], x, y));
		}
		if (ans < 1e-7)
			ans = 0;
		cout << fixed << setprecision(15) << ans << '\n';
	}
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.605291072916640
0.977772290465605
1.551845105401790
1.414213562373095

result:

ok 4 numbers

Test #2:

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

input:

1 8 32
7
0 1
1 0
0 -1
-1 0
1 -1
-1 1
-1 -1
1 1
20 10
10 20
-20 10
10 -20
-10 20
20 -10
-10 -20
-20 -10
2 1
1 2
-2 1
1 -2
-1 2
2 -1
-1 -2
-2 -1
5 0
0 5
-5 0
0 -5
5 5
5 -5
-5 5
-5 -5
9 0
0 9
-9 0
0 -9
9 9
9 -9
-9 9
-9 -9

output:

15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
2.00...

result:

ok 32 numbers

Test #3:

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

input:

3 4 1681
16
8
4
-1 0
0 -1
0 1
1 0
-9 17
-4 -7
2 -13
-11 -17
15 -19
-7 1
-8 14
-8 -7
-8 20
-16 -3
12 14
-3 12
9 -5
-18 11
3 -1
2 0
-18 0
0 -19
-1 -19
18 -8
2 20
5 -8
-8 -19
-9 -16
20 -19
14 -1
3 10
-1 -4
4 10
16 17
19 -7
-17 4
1 -12
-5 -12
-5 -10
-15 -5
-10 -19
-2 -10
-4 -16
-2 4
-14 8
-17 16
4 1
16 ...

output:

9.055385138137417
4.123105625617661
3.605551275463989
11.045361017187261
15.297058540778354
1.414213562373095
8.246211251235321
7.000000000000000
8.944271909999159
3.000000000000000
12.165525060596439
5.000000000000000
5.099019513592785
11.180339887498948
1.414213562373095
2.000000000000000
2.000000...

result:

ok 1681 numbers

Test #4:

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

input:

3 4 1681
16
8
4
-1 -1
1 -1
-1 1
1 1
17 1
13 7
-13 -18
-1 18
4 -12
-9 3
5 10
-10 1
-12 -4
14 10
-18 19
0 -3
-7 3
-16 11
-15 9
16 1
-8 -12
3 1
0 -2
15 -18
-14 20
9 -19
17 12
20 5
-3 -6
12 -1
9 10
-13 -9
-20 -15
-11 6
17 -2
-10 -19
15 -8
-6 17
18 15
2 -3
18 -12
8 -3
-11 -6
19 -15
20 0
3 4
2 -16
-6 -17
...

output:

11.777372119303551
4.631593682590214
6.895656100977256
12.291422905366941
6.555964003580544
4.270304206047021
4.392536000447645
6.367825885745278
6.555964003580544
2.990316379370501
10.187520359495127
2.833626166508712
2.977064831365349
4.696779860161953
4.352239888693120
11.328455809796768
3.384030...

result:

ok 1681 numbers

Test #5:

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

input:

1 4 16
7
0 1
1 0
0 -1
-1 0
3 0
0 3
-3 0
0 -3
3 3
3 -3
-3 3
-3 -3
8 0
0 8
-8 0
0 -8
8 8
8 -8
-8 8
-8 -8

output:

4.000000000000000
4.000000000000000
4.000000000000000
4.000000000000000
5.000000000000000
5.000000000000000
5.000000000000000
5.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
8.062257748298550
8.062257748298550
8.062257748298550
8.062257748298550

result:

ok 16 numbers

Test #6:

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

input:

30 4 120
128
1
2
256
4
512
1024
2048
8
4096
32768
131072
262144
524288
8192
268167
16
536334
16384
1047
32
2095
8380
64
134083
65536
4190
67041
33520
16760
536334 0
-536335 0
0 536334
0 -536335
-1 1
-2 2
-4 4
-8 8
-16 16
-32 32
-64 64
-128 128
-256 256
-512 512
-1024 1024
-2048 2048
-4096 4096
-8192...

output:

1.000000000000000
2.000000000000000
4.000000000000000
8.000000000000000
16.000000000000000
32.000000000000000
64.000000000000000
128.000000000000000
256.000000000000000
512.000000000000000
1024.000000000000000
2048.000000000000000
4096.000000000000000
8192.000000000000000
16384.000000000000000
32768...

result:

ok 120 numbers

Test #7:

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

input:

4 4 1681
1000
1
999000
999
999000 999000
-999001 999000
999000 -999001
-999001 -999001
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18...

output:

8.393071595899558
16.453441243476639
14.475640085235758
19.043231368144237
16.182932417451168
19.043231368144237
19.010576536590187
3.305893553660572
11.763187620795244
14.667308360055634
16.295525639797088
7.617705510947693
16.692652903019119
25.870057685088936
16.182932198759698
20.084870431584898...

result:

ok 1681 numbers

Test #8:

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

input:

3 3 108
8
16
4
0 1
0 -1
-1 0
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
0 -8
0 -9
0 -10
0 -11
0 -12
0 -13
0 -14
0 -15
0 -16
0 -17
0 -18
0 -19
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16...

output:

4.000000000000000
3.000000000000000
2.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
3.000000000000000
4.000000000000000
3.000000000000000
2.000000000000000
1.000000000000000
0.0000000000...

result:

ok 108 numbers

Test #9:

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

input:

3 3 1681
8
16
4
-1 0
0 1
0 -1
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18 7
6 -3
-9 -9
-8 -12
-16 20
-1 -13
14 20
-7 -14
13 -14
19...

output:

9.219544457292887
3.162277660168379
15.033296378372908
6.708203932499369
6.000000000000000
19.104973174542800
12.000000000000000
1.000000000000000
5.656854249492380
4.123105625617661
1.414213562373095
5.099019513592785
12.369316876852982
19.235384061671345
6.000000000000000
9.486832980505138
6.32455...

result:

ok 1681 numbers

Test #10:

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

input:

3 2 1681
16
8
4
0 1
0 -1
-1 -17
-18 -12
4 -6
12 17
-14 -11
-10 19
-19 -15
-15 -17
2 13
-8 -13
-18 7
-17 12
-20 16
3 12
-13 13
10 5
18 -9
-16 4
1 17
-19 -6
-17 -4
12 -18
-10 -17
-9 -20
13 6
11 0
4 5
2 -15
8 -12
1 9
17 -10
1 -13
-8 1
-12 11
5 0
20 -16
-5 8
-13 -2
7 12
-8 14
-4 9
10 -11
19 -3
-18 8
-4 ...

output:

1.414213562373095
18.439088914585775
4.472135954999579
12.041594578792295
14.317821063276353
10.440306508910550
19.026297590440448
15.033296378372908
3.605551275463989
8.544003745317531
18.027756377319946
17.464249196572981
20.000000000000000
5.000000000000000
13.341664064126334
10.049875621120890
1...

result:

ok 1681 numbers

Test #11:

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

input:

3 2 1681
16
8
4
-1 -999001
0 1
13 -1
-7 19
19 -13
17 -1
-14 14
18 -9
10 -10
11 20
6 16
-16 7
14 -7
-3 4
7 -14
-20 2
14 -6
13 16
-16 -13
2 0
-8 20
-3 20
0 14
-18 1
-15 12
-3 -12
-13 -14
14 0
12 4
-14 9
-10 -9
20 15
-20 0
19 4
16 -8
3 -14
19 -15
-11 19
6 -9
-17 -5
-17 13
18 12
6 12
-16 -10
12 7
8 -6
-...

output:

13.341667965588257
7.615773105863908
19.235399881681894
17.262680444705100
14.142135623730950
18.027764372990675
10.198046879676520
11.704699910719625
6.000000000000000
16.031219541881397
14.035676835267186
3.000000000000000
7.280125289047176
20.099751242241781
14.142139587489014
13.000000000000000
...

result:

ok 1681 numbers

Test #12:

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

input:

3 2 1
1
2
4
0 1
0 -1
-7 0

output:

7.071067811865475

result:

ok found '7.0710678', expected '7.0710678', error '0.0000000'

Test #13:

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

input:

3 2 1
1
2
4
0 1
-1 -999001
-7 0

output:

7.071066820925964

result:

ok found '7.0710668', expected '7.0710668', error '0.0000000'

Test #14:

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

input:

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

output:

0.000000000000000
0.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
3.000000000000000
4.000000000000000
5.000000000000000
6.000000000000000
7.000000000000000
8.000000000000000
9.0000000000...

result:

ok 36 numbers

Test #15:

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

input:

4 5 8
8
1
2
4
0 1
1 1
1 -1
-3 2
-2 -5
-4 0
-4 -1
-4 -2
-8 -1
-8 -2
-8 -3
-8 -4
-9 -3

output:

2.318273189507441
3.147379239223551
3.043003664556540
5.601139657637513
6.294758478447102
6.553438496857290
6.086007329113080
7.480164533118013

result:

ok 8 numbers

Test #16:

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

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.998865701868704
14.525423018761117
21.073102117794251
31.843189113241067
115.924895013615673
49.991391054939894
60.506629716441605
69.958130039585846
134.902308151242212
90.172561431422950
100.220151411668208
110.154852885070047
119.838138057650303
169.259259924830494
139.857713809972359
149.9038...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 124ms
memory: 5660kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.000000000000000
15.295841308968246
21.472081503158730
30.839308519800434
35.006555272523730
50.931458107477317
60.506619828997751
70.363795442201725
80.007038937115761
90.056171321627367
100.000633293051919
110.050508279773909
119.838128085721262
129.885197989281585
134.868076476158608
149.833874...

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 127ms
memory: 5636kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.000000000000000
11.793537328942145
15.006851569378945
30.316874089052133
40.113906820859334
50.140933717450126
60.175584315259198
70.363795442201725
80.125534801392465
89.856351459773306
100.000633293051919
109.955169614314125
119.767282240876358
129.812131979221724
139.932670846875566
149.713860...

result:

ok 99999 numbers

Test #19:

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

input:

3 3 1781
27448
700036
1565
727561 561893
946824 -149222
20811 -112456
-864128 96532
16 -3
-17 6
-20 20
-13 -9
3 1
6 6
-18 -10
-10 0
-4 2
19 -11
-3 18
9 -6
-14 -5
-17 1
-16 -7
20 6
20 10
0 -8
-15 20
-12 17
-8 -13
14 -8
-14 -4
20 -12
-11 0
-7 13
1 -4
-1 17
20 4
-17 12
-3 -4
8 3
-9 -9
-11 14
-12 14
-13...

output:

869958.248114476979993
1548.728110911664889
1574.070850191947786
1568.855156609634849
1558.582578139035297
1562.014764098693464
1556.584271779073085
1558.564638007550467
1566.850548158155620
1566.948507823863285
1544.539412209167181
1556.455197783836330
1555.182232268123369
1562.699966582056270
1569...

result:

ok 1781 numbers

Test #20:

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

input:

2 2 1781
455464
989237
648422 -984508
-86934 -353141
15 -8
12 -16
-20 -3
-5 15
6 -9
19 -16
-16 5
6 6
3 16
-2 -4
-19 -5
-1 -5
5 -11
0 1
9 9
5 13
3 -15
10 -17
16 -20
2 15
9 -2
0 5
18 -6
-20 18
3 -8
-7 -2
13 -8
15 -13
885672 69814
893942 -786043
13 1
2 7
15 20
-12 -2
679345 587036
-20 8
-9 -9
0 17
15 -...

output:

455449.068343449275716
455444.037305271015072
455456.306609651423855
455477.370048753881235
455453.183515037673487
455440.187062228541151
455465.030764936369224
455465.710642614713237
455475.712201902747296
455459.637885071202504
455454.603568764108644
455458.905910793023423
455452.063287644227330
4...

result:

ok 1781 numbers

Test #21:

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

input:

4 4 1781
284368
639066
544427
453079
-473316 -385890
-403701 -456998
341400 289506
328542 749626
-11 0
15 -5
18 -15
4 18
-12 -15
-2 9
3 -20
-5 0
-5 8
14 -8
-247884 -376851
-14 -7
-2 19
18 5
4 -17
-17 10
-5 14
7 -6
4 0
13 -14
6 7
-17 19
2 20
-17 2
-18 -6
-14 -13
-2 17
16 -9
8 -13
12 5
850219 294605
2...

output:

284359.474486080791365
284359.793732645160645
284363.973878313397847
284349.908226094149853
284348.813509705685988
284360.559810770306200
284354.997431616959688
284364.124745337440004
284362.680004575557206
284362.496790819477155
64050.720210684561902
284352.725997149006645
284351.400949598880203
28...

result:

ok 1781 numbers

Test #22:

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

input:

5 5 1781
855105
811761
393138
763609
395482
485837 -963055
-805058 420348
-996068 26540
957233 158478
40565 268210
19 -11
16 9
-8 -7
-15 -2
10 0
-19 -1
-5 4
-14 5
20 6
-10 -16
10 -1
-17 -6
16 -19
11 -20
-11 -20
7 -5
9 -16
7 -10
388718 -210265
-7 -12
1 6
-4 -7
-11 15
-4 -11
5 16
-1 -17
-15 9
-2 1
17 ...

output:

393119.621394643046983
393120.744903681625516
393130.189351588748224
393123.058599690699765
393128.134296897345251
393119.033379073073206
393131.716431363734984
393123.275621858658781
393117.288585386112459
393128.219226072018586
393128.297637329649177
393121.165896118341834
393113.829886579257362
3...

result:

ok 1781 numbers

Test #23:

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

input:

4 4 1781
360226
923659
843797
234702
385835 56098
-255808 -788591
-223435 302545
-943925 -181801
-1 -5
0 -16
7 -8
-13 0
-14 -17
0 17
-5 10
-14 -13
-4 -1
-14 -12
-19 0
-3 9
19 -20
-11 -13
746464 508236
-244133 857457
-9 -18
0 -6
8 12
-15 -18
-552127 -210744
-7 -1
-7 13
13 -18
-16 -18
3 10
8 11
2 0
18...

output:

234696.935415039393035
234686.780762982774093
234696.224052096822291
234689.234624189158296
234681.509833541270254
234688.325222284388957
234690.985530420926125
234685.314701468789110
234697.883062973601724
234685.983333384637376
234683.342920964368886
234692.978097465063797
234686.076394613965178
2...

result:

ok 1781 numbers

Test #24:

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

input:

2 2 1781
724290
427620
585285 -84915
-522957 846042
2 -4
5 -13
18 14
-5 -11
-18 4
9 12
6 9
-13 18
14 18
-2 19
17 6
17 10
5 -20
0 -7
-3 -7
-3 20
-7 11
-11 -14
7 -8
17 -5
-8 -19
-6 13
17 15
5 12
4 -18
-2 11
0 12
0 1
3 -8
11 6
-8 19
-10 11
-15 -8
-6 -18
20 -18
16 -16
16 2
-19 -10
-13 -12
-2 14
5 -18
-2...

output:

427617.446418637142528
427613.185439975044488
427604.196937802469591
427623.368971969593076
427607.133601538887461
427612.816413233068744
427615.354498480043588
427597.853682650099586
427608.729955872431020
427602.786779337812050
427604.037703262545961
427604.612118823957161
427612.180633454641367
4...

result:

ok 1781 numbers

Test #25:

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

input:

4 4 1781
509841
4372
912999
543071
445967 -716460
-693896 -395076
-734650 644244
-86759 -207195
-14 -17
1 -4
9 -5
-20 -7
12 4
0 17
0 19
2 -8
10 11
-10 1
-14 -6
-13 -1
-3 11
-8 -11
-10 11
-13 5
4 -14
-977857 62664
-16 0
5 -11
-19 -7
-1 -11
9 -11
-20 13
-1 8
-2 5
10 19
19 0
20 -9
-20 -20
6 -2
17 -6
-5...

output:

4350.916516885702594
4368.075870665845946
4363.002009875000863
4351.157856369776465
4369.071821570437296
4360.810115602476067
4359.496128618513616
4364.152108232064847
4372.291164919348957
4363.808491637303434
4356.865406077191372
4360.211548211098620
4362.496344194203422
4358.764831637725666
4357.2...

result:

ok 1781 numbers

Test #26:

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

input:

1 1 1781
730978
522802 -441174
-7 19
-5 -12
13 -4
12 17
-4 -16
-18 13
5 -6
-15 11
13 -10
1 -1
12 -14
-2 0
13 4
20 14
-3 18
-6 1
873868 299053
-13 7
-14 -5
5 20
12 4
-6 -4
-12 14
-1 -10
-9 10
-13 -12
-18 6
11 -4
13 13
11 14
-3 16
14 -4
13 0
14 19
-18 4
4 -19
19 -16
-6 11
-20 17
-3 13
-10 8
857606 -57...

output:

730995.603325437440674
730974.082282885132315
730965.485102324044021
730979.792987545942594
730970.738391330580896
731000.140459052441713
730970.309227254064581
730996.557869047915290
730961.615551213763922
730976.590829609719663
730959.800117169367127
730979.528497912748151
730970.644548550406398
7...

result:

ok 1781 numbers

Test #27:

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

input:

1 1 1781
372082
-541795 -869565
281973 459007
739644 385456
1 18
-14 16
-17 10
19 -13
-14 -20
19 -3
-6 -11
-17 5
-3 -10
-5 4
17 -3
-11 -16
-7 -19
-11 14
-8 5
8 0
-1 -3
11 -12
-9 13
-2 11
-11 -11
12 20
-9 -20
-12 -11
541236 905488
19 16
-9 -14
9 12
-18 17
3 20
16 8
-15 14
-20 17
-4 -4
14 -1
1 -2
-17 ...

output:

910776.206267791914911
1169879.348474515206931
372097.806162880731449
372088.176890145037078
372081.497990245673208
372081.014669749227465
372057.621846727057147
372089.501738643153857
372069.491004181666568
372077.254180424742515
372071.926200642954370
372082.750912222626397
372088.444027550949443
...

result:

ok 1781 numbers

Test #28:

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

input:

4 4 1781
8
4
5
6
-7 -2
5 10
1 5
-5 3
14 -16
-17 8
10 3
10 1
-17 -1
-7 -10
-8 5
-20 -12
20 11
16 5
7 -20
10 8
-3 12
17 4
1 16
2 -14
10 -13
-4 12
-4 -11
-11 2
1 -13
-5 -11
9 -20
1 15
5 15
-11 13
2 4
-19 2
10 12
-12 8
19 -1
-14 0
-5 6
2 -1
0 13
-5 -2
-9 8
11 9
-2 -15
-4 -8
0 0
-13 -8
-5 -20
64289 -8949...

output:

23.073767740704896
10.858474455993558
7.649399947186104
8.504961407320144
9.384559030414698
7.832875423536833
1.442652097559291
15.734226393396022
16.866311506195664
12.607900073843284
21.791970094608372
6.477587843635739
6.175927845593418
13.788203719122256
8.175175157812430
14.163884242599091
18.2...

result:

ok 1781 numbers

Test #29:

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

input:

2 2 1781
2
6
9 9
4 0
-6 -15
16 -2
-11 2
-955131 926039
-6 5
-9 0
-10 -1
13 -5
-10 12
0 -3
-13 -12
-18 -5
-2 -6
-8 10
13 13
2 16
13 6
-2 2
9 -8
-397859 -12783
-6 14
-7 -8
-1 15
-20 7
-16 -14
54141 265024
15 -19
-18 7
-3 14
-4 16
7 10
-15 15
19 5
0 5
-1 -5
-20 -15
-5 6
10 -19
-7 7
-17 7
19 -15
17 14
3...

output:

17.000000000000000
10.198039027185570
12.428026557853653
1330347.149796098113598
8.235801547192974
10.509797530053360
11.666734691943933
8.602325267042627
15.567374401308257
3.605551275463989
19.209372712298546
20.446364563637282
7.211102550927979
12.741394968782171
12.384776310850236
11.96933311691...

result:

ok 1781 numbers

Test #30:

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

input:

4 4 1781
9
2
19
5
-6 -1
-1 -8
-5 -2
-4 9
-3 20
18 -20
-20 -17
20 4
-7 12
12 -2
-2 -16
-9 15
13 11
-18 10
-14 -18
-5 8
20 14
-11 -4
2 16
-14 17
0 14
7 -6
5 3
5 -19
-8 4
-1 -12
18 6
-18 -1
-19 -7
13 6
-19 -3
-12 -2
8 15
4 1
0 -6
-12 -12
8 -13
20 -12
11 18
5 -9
-15 -20
19 -17
3 3
18 -15
14 -14
-8 -8
16...

output:

5.404020532761839
20.388932589928075
10.219556644123654
20.925345696220928
5.044131121936667
12.248079206413252
2.875484503402901
2.688505513510126
16.348661420395246
12.647248742068139
11.533394028768596
1.363332334345770
23.964433571521225
2.724240537695449
9.614741742516543
6.293812489332659
6.83...

result:

ok 1781 numbers

Test #31:

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

input:

1 1 1781
3
9 5
-8 -13
-5 1
12 2
12 -3
2 -13
-4 -1
11 -1
-18 -11
-160154 122064
8 1
6 -7
-1 -16
-19 -10
0 19
-6 -6
8 -11
5 20
-9 17
-12 11
-7 8
-16 5
-6 4
4 -9
-12 17
1 11
-8 15
2 6
10 17
-19 -15
4 17
-16 11
16 -17
-4 7
-20 11
-14 7
-8 -20
15 17
-7 16
338371 -987896
75680 -112362
-7 20
-17 1
3 20
-3 ...

output:

17.939891245093074
7.636154837126755
9.393240172863978
10.382786181004820
14.470323469725024
7.063542469185607
8.730376702242023
24.092766949416910
201368.836075977485095
5.396905887552088
9.106445034651403
17.828815581801218
24.470237133067861
17.738001743309079
11.399684533477499
13.56808329145852...

result:

ok 1781 numbers

Test #32:

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

input:

1 1 1781
10
-8 7
5 1
2 -17
-14 -9
-13 -19
-18 11
14 -16
12 -12
18 2
15 2
-17 -20
-18 9
-13 5
18 -2
11 -4
-13 -17
18 5
13 -12
868693 773239
-17 -8
-10 18
-1 2
5 -2
-4 0
17 -19
-8 -7
-4 -4
197365 28813
-1 17
5 5
-18 10
-8 19
-13 -7
14 9
-7 5
7 -16
14 14
17 18
-7 1
6 -12
18 18
-8 -6
16 -20
-4 -10
-5 1
...

output:

13.714502444978360
25.436089213233454
16.876295650953958
26.164132134780405
11.366678326338350
31.200047260154136
26.956622796969487
25.934290539356100
22.987666782370990
28.222788078910077
10.749026025142498
5.699087522521474
26.930796393891079
21.336523649952786
24.212014084984915
25.5749320489346...

result:

ok 1781 numbers

Test #33:

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

input:

1 1 1781
2
3 -8
-17 2
-5 9
19 -20
2 5
-15 -20
-5 -6
-11 0
-17 -13
17 2
3 -16
12 -12
17 17
13 10
12 13
-10 -12
12 -4
-1 0
0 -7
-8 -13
13 5
-20 14
8 -20
-14 1
-7 7
11 -18
18 -10
-15 -6
15 12
15 -17
10 11
-153064 -395673
19 -5
-10 13
3 5
-4 11
5 -12
2 15
-15 -15
-13 18
720298 994936
9 0
2 -15
-1 -17
13...

output:

18.120900293543999
12.277227668502912
25.756713381830351
6.994111524609381
23.982515970802145
7.039216474161792
11.851136292773332
20.909023812565242
16.751544388280793
14.312981916306624
15.172418208065683
24.935797361357515
17.093704927258029
18.677130187406938
14.734352280986821
11.49629540167842...

result:

ok 1781 numbers

Test #34:

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

input:

5 5 1781
1
2
5
6
7
-7 -4
2 7
-8 -6
4 -3
-7 6
-2 18
0 -9
7 -9
-17 8
20 -15
0 1
-19 -4
-978084 306093
0 19
4 1
4 12
-14 1
18 6
18 8
-9 0
-11 16
-17 0
-16 4
-4 -8
20 11
4 -16
1 1
-3 2
16 -17
13 10
17 11
11 -1
0 -12
-2 17
-7 6
4 20
-3 -2
-6 -7
-11 19
-9 -11
-7 -17
7 -6
2 -6
19 -19
12 -6
1 -9
-11 -13
1 -...

output:

11.932650869594700
7.211102550927979
5.000000000000000
12.182294316342506
18.000000000000000
0.277402423778801
12.933040773418723
1024855.136242259555956
12.419123557141262
3.255764119219941
5.663885030090965
9.097817830699935
16.056151469141041
16.126983401556800
4.538872557399926
12.77877989409033...

result:

ok 1781 numbers

Test #35:

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

input:

1 1 1781
3
7 -6
-1 -12
-13 18
-13 14
18 10
13 -13
0 15
5 15
15 -6
-19 -8
-18 7
-19 13
-9 -8
-14 3
-4 -19
-19 -14
19 -18
-16 -19
2 -1
17 18
10 -18
15 9
-750503 54264
4 -19
-4 -16
4 -20
-7 -6
16 4
-14 -14
6 10
2 -17
-18 -20
-10 -5
9 13
16 14
15 -18
-9 -6
12 3
-15 20
-16 7
-13 -4
6 17
-6 3
10 -1
-20 -1...

output:

10.568753981684030
25.129812639925068
22.088197987948100
19.749627068679198
15.395332340873364
17.104713491053779
17.169552281293717
13.350596104395805
22.120516873340852
22.166031461238223
26.006095050953139
12.796947706458737
17.014458537399665
18.166781274699894
24.451764298294356
23.176696895742...

result:

ok 1781 numbers

Test #36:

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

input:

3 3 1781
1
5
6
1 0
2 4
-10 10
0 -2
1 14
12 18
19 16
2 -9
-15 8
0 -5
1 -19
-12 8
-10 -3
-12 19
390267 -598135
15 12
3 8
10 -9
-16 -7
-8 13
0 6
-10 4
-2 20
-12 9
-3 6
-158495 -417843
-14 -15
-14 17
-3 10
11 4
-18 14
-20 16
1 -18
13 -17
8 5
-6 -19
4 0
-953821 -473693
15 10
-7 -10
18 8
-7 -3
6 15
4 -6
1...

output:

2.236067977499790
8.796002999431880
15.697291772532746
19.475761334387566
9.055385138137417
11.394671052404843
5.099019513592785
19.000000000000000
8.619418339727374
9.192525513532267
16.672020795290663
714191.239337196014560
13.989425910523265
2.652414037440156
9.848857801796105
16.267528012327284
...

result:

ok 1781 numbers

Test #37:

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

input:

3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

output:

0.977772290465605
2.750120773895214
0.846777708005352
1.464071052923670
0.585786437626905

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 36ms
memory: 5764kb

input:

99996 100000 100
524288
524290
262146
524291
786444
262156
262160
262169
262170
524314
786460
524317
786463
786464
786465
786473
262192
262195
262196
524341
524343
524347
786493
524351
524352
524354
524358
786504
262218
524363
786510
262227
524374
262234
262237
786526
524385
786531
262243
262244
262...

output:

6.462488165036192
15.750796763306542
53.678242235052209
82.368444069275990
13.983800968730759
37.949624407787930
19.417382739876514
26436.954804314449561
16.276546052020426
17.455115463849599
41.139742618248598
10.886385126879571
2.541277018583687
43.124079192295858
91.936832737997983
29490.05864559...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 133ms
memory: 5368kb

input:

100 100000 100000
519684
153097
817673
204302
50193
548881
600598
61977
360473
18978
943676
632382
60487
846418
325716
742485
16470
330336
240737
978021
385642
786539
871532
153708
561268
22644
795771
122496
468609
60545
617602
768142
385680
370839
482970
101019
67740
237725
915618
576686
501937
630...

output:

88245.972263364388667
1395.006262689433353
65837.716040132988248
3799.085782635251375
3433.758283839787170
194.090692227499194
7369.210725630295035
265305.153138388887044
8568.334302155730211
4911.650769248802433
54497.524328931921353
3603.753680499854058
3575.120818854348440
159352.017849327979306
...

result:

ok 100000 numbers

Test #40:

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

input:

99996 100 100000
262144
262145
262148
262156
786446
262163
262170
262171
524318
786463
262175
262176
524322
524323
524335
262193
262198
524343
262200
524352
786508
262220
786509
786516
524375
524378
262237
262238
262240
786528
786529
786530
524388
262245
786542
786546
262259
786548
262265
524410
524...

output:

5994.636172539126487
5614.804600055703119
18063.491359815856027
48666.350136998642760
29146.202153790202861
1712.932520099817544
166623.047461909952048
37945.226124340107052
14861.689749269426644
52982.283561519559896
2858.978120407578575
13281.349540431645432
2313.817285228547819
9696.1464429239381...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 115ms
memory: 5660kb

input:

100000 100000 99999
786438
524295
262152
9
786447
524304
262161
18
786456
524313
262170
27
786465
524322
262179
36
786474
524331
262188
45
786483
524340
262197
54
786492
524349
262206
63
786501
524358
262215
72
786510
524367
262224
81
786519
524376
262233
90
786528
524385
262242
99
786537
524394
262...

output:

7.000000000000000
7.000000000001587
7.000000000001587
7.000000000000000
9.000000000000000
9.000000000000000
9.000000000000000
9.000000000000000
1.007620982403236
2.000000000000000
11.401762144590732
11.401754250991380
8.006305499963675
9.000010000100001
9.000000000000000
20.124611797498107
0.1107702...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 151ms
memory: 5672kb

input:

95165 100000 100000
524289
524290
3
524291
5
524297
786442
524300
786447
262161
524325
41
786474
43
524340
262201
524347
524351
524352
68
786502
786505
75
262228
262230
89
262233
91
92
524382
95
786530
262250
109
524401
113
786547
114
262261
786550
262267
123
262271
127
524420
786565
524421
524424
2...

output:

4.869296048246171
10.547084101693438
20.338245462779162
11.047239177444610
29307.643746329081962
8.696939182885023
12.982205241161177
42.208825685683746
18.284846836654149
1.324501422857478
89248.113329288446799
10.698730258099551
12.063924232591900
82.456790890854387
0.273929450543618
4.08210215696...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 153ms
memory: 5636kb

input:

95136 100000 100000
786432
524296
262156
524313
786458
262171
31
262178
38
262184
524332
524333
262197
262203
524348
786494
524350
262208
65
524359
262215
262217
524363
786515
524377
786524
96
97
262243
524389
524392
104
786538
107
786539
524396
110
117
262264
121
786559
128
262274
131
524422
262279...

output:

276808.618140549220811
10.735444517532355
2.729671499338328
305762.777518170212261
18.130777790201207
24.254768209468655
9.750601630241540
7.181199237333779
9.185528210606823
51.864042051999241
57.784192180242414
304131.586405272125631
91.131096195772950
21.511942220493136
5.610489981790155
13.29664...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 152ms
memory: 5640kb

input:

95116 100000 100000
786432
524298
13
262159
19
21
786455
28
524322
36
37
262182
262185
786475
786479
524340
786488
524350
262209
524354
786511
262224
786512
524369
524371
80
262229
524374
524376
262233
95
524384
262241
786531
262243
524390
786536
524394
524395
106
262255
112
262257
114
117
786551
78...

output:

2.040233125615756
17.842584580958997
17.075114544418186
11.280952583055351
219404.306297076978055
27.077625533511486
228139.775011337774018
14.189689595196904
32.151684769750846
13.958807259076544
30.474901572722785
352634.110645619148102
220634.768760059418142
67.337972452782988
65.610884685239735
...

result:

ok 100000 numbers