QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187051#3854. RadarrealIyxiang#AC ✓200ms7072kbC++141.8kb2023-09-24 14:07:132023-09-24 14:47:53

Judging History

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

  • [2023-09-24 14:47:53]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:200ms
  • 内存:7072kb
  • [2023-09-24 14:07:13]
  • 评测
  • 测评结果:0
  • 用时:156ms
  • 内存:6544kb
  • [2023-09-24 14:07:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
typedef double db; 
const int N = 2e5 + 5; 
const db PI = acos(-1.0); 
int R, F, n, x, y; 
db ans, r[N], ang[N]; 

db dist (db x_1, db y_1, db x_2, db y_2) {
  return sqrt((x_1 - x_2) * (x_1 - x_2) + (y_1 - y_2) * (y_1 - y_2)); 
}
db gan (db x, db y) {
  if(x == 0) return (y > 0 ? PI / 2 : PI * 3 / 2); 
  else if(x >= 0 && y >= 0) return atan(y / x); 
  else if(x < 0 && y >= 0) return PI - atan(y / (-x)); 
  return gan(-x, -y) + PI; 
}
void chk (db r, db ang) {
  db nx = r * cos(ang), ny = r * sin(ang); 
  // printf("%.10f %.10f %.10f %.10f %.10f\n", x, y, nx, ny, ang); 
  ans = min(ans, dist(x, y, nx, ny)); 
}
void chk (db ang) {
  db dx = cos(ang), dy = sin(ang); 
  db rr = 1.0 * x * dx + 1.0 * y * dy; 
  int l1 = upper_bound(r + 1, r + R + 1, rr) - r - 1; 
  int r1 = lower_bound(r + 1, r + R + 1, rr) - r; 
  if(l1) chk(r[l1], ang); 
  if(r1 <= R) chk(r[r1], ang); 
}

int main () {
  scanf("%d%d%d", &R, &F, &n); 
  rep(i, 1, R) scanf("%lf", &r[i]); 
  sort(r + 1, r + R + 1); 
  rep(i, 1, F) {
    scanf("%d%d", &x, &y); 
    ang[i] = gan(x, y), ang[i + F] = ang[i] + 2.0 * PI; 
    // printf("%d %d %.10lf\n", x, y, ang[i]); 
  }
  F *= 2; 
  sort(ang + 1, ang + F + 1); 
  rep(i, 1, n) {
    scanf("%d%d", &x, &y); 
    ans = 1e16; 
    db A = gan(x, y);
    int l = upper_bound(ang + 1, ang + F + 1, A) - ang - 1; 
    int r = lower_bound(ang + 1, ang + F + 1, A) - ang; 
    if(l && l <= F) chk(ang[l]); 
    if(r && r <= F) chk(ang[r]);  
    A += PI * 2;
    l = upper_bound(ang + 1, ang + F + 1, A) - ang - 1; 
    r = lower_bound(ang + 1, ang + F + 1, A) - ang; 
    if(l && l <= F) chk(ang[l]); 
    if(r && r <= F) chk(ang[r]);  
    printf("%.12lf\n", ans); 
  }
  return 0; 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.605291072917
0.977772290466
1.551845105402
1.414213562373

result:

ok 4 numbers

Test #2:

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

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.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
2.000000000000
2.000000000000
2.000000000000
2.00000...

result:

ok 32 numbers

Test #3:

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

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.055385138137
4.123105625618
3.605551275464
11.045361017187
15.297058540778
1.414213562373
8.246211251235
7.000000000000
8.944271909999
3.000000000000
12.165525060596
5.000000000000
5.099019513593
11.180339887499
1.414213562373
2.000000000000
2.000000000000
3.000000000000
3.162277660168
8.246211251...

result:

ok 1681 numbers

Test #4:

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

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.777372119304
4.631593682590
6.895656100977
12.291422905367
6.555964003581
4.270304206047
4.392536000448
6.367825885745
6.555964003581
2.990316379370
10.187520359495
2.833626166509
2.977064831365
4.696779860162
4.352239888693
11.328455809797
3.384030147710
1.836459365744
2.947251516416
7.635131895...

result:

ok 1681 numbers

Test #5:

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

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.000000000000
4.000000000000
4.000000000000
4.000000000000
5.000000000000
5.000000000000
5.000000000000
5.000000000000
1.000000000000
1.000000000000
1.000000000000
1.000000000000
8.062257748299
8.062257748299
8.062257748299
8.062257748299

result:

ok 16 numbers

Test #6:

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

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.000000000000
2.000000000000
4.000000000000
8.000000000000
16.000000000000
32.000000000000
64.000000000000
128.000000000000
256.000000000000
512.000000000000
1024.000000000000
2047.999999999999
4095.999999999999
8191.999999999997
16383.999999999995
32767.999999999989
65535.999999999978
131071.99999...

result:

ok 120 numbers

Test #7:

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

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.393071595900
16.453441243477
14.475640085236
19.043231368144
16.182932417451
19.043231368144
19.010576536590
3.305893553661
11.763187620795
14.667308360056
16.295525639797
7.617705510948
16.692652903019
25.870057685089
16.182932198760
20.084870431585
10.694511684541
19.295116007469
23.759261884935...

result:

ok 1681 numbers

Test #8:

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

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.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
...

result:

ok 108 numbers

Test #9:

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

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.219544457293
3.162277660168
15.033296378373
6.708203932499
6.000000000000
19.104973174543
12.000000000000
1.000000000000
5.656854249492
4.123105625618
1.414213562373
5.099019513593
12.369316876853
19.235384061671
6.000000000000
9.486832980505
6.324555320337
4.123105625618
18.027756377320
4.4721359...

result:

ok 1681 numbers

Test #10:

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

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.414213562373
18.439088914586
4.472135955000
12.041594578792
14.317821063276
10.440306508911
19.026297590440
15.033296378373
3.605551275464
8.544003745318
18.027756377320
17.464249196573
20.000000000000
5.000000000000
13.341664064126
10.049875621121
18.027756377320
16.000000000000
1.414213562373
19...

result:

ok 1681 numbers

Test #11:

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

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.341667965588
7.615773105864
19.235399881682
17.262680444705
14.142135623731
18.027764372991
10.198046879677
11.704699910720
6.000000000000
16.031219541881
14.035676835267
3.000000000000
7.280125289047
20.099751242242
14.142139587489
13.000000000000
16.278804854418
4.472135955000
8.944271909999
5....

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.071067811865

result:

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

Test #13:

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

input:

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

output:

7.071066820926

result:

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

Test #14:

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

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.000000000000
0.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
5.000000000000
6.000000000000
7.000000000000
8.000000000000
9.000000000000
10.000000000000
1.414213562373
2.236067977500...

result:

ok 36 numbers

Test #15:

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

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.318273189507
3.147379239224
3.043003664557
5.601139657638
6.294758478447
6.553438496857
6.086007329113
7.480164533118

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 98ms
memory: 6576kb

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.998865701869
14.525423018761
21.073102117794
31.843189113241
115.924895013616
49.991391054940
60.506629716442
69.958130039586
134.902308151242
90.172561431423
100.220151411668
110.154852885070
119.838138057650
169.259259924831
139.857713809972
149.903862612096
159.813034019318
169.924008912966
20...

result:

ok 99999 numbers

Test #17:

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

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.000000000000
15.295841308968
21.472081503159
30.839308519800
35.006555272524
50.931458107477
60.506619828998
70.363795442202
80.007038937116
90.056171321627
100.000633293052
110.050508279774
119.838128085721
129.885197989282
134.868076476159
149.833874636269
159.950469676917
169.923998940019
174....

result:

ok 99999 numbers

Test #18:

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

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.000000000000
11.793537328942
15.006851569379
30.316874089052
40.113906820859
50.140933717450
60.175584315259
70.363795442202
80.125534801392
89.856351459773
100.000633293052
109.955169614314
119.767282240876
129.812131979222
139.932670846876
149.713860056673
159.753646614700
169.738741224847
179....

result:

ok 99999 numbers

Test #19:

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

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.248114477028
1548.728110911665
1574.070850191948
1568.855156609635
1558.582578139035
1562.014764098693
1556.584271779073
1558.564638007550
1566.850548158156
1566.948507823863
1544.539412209167
1556.455197783836
1555.182232268123
1562.699966582056
1569.163895394819
1561.121016860294
1545.52168...

result:

ok 1781 numbers

Test #20:

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

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.068343449268
455444.037305271020
455456.306609651423
455477.370048753859
455453.183515037643
455440.187062228506
455465.030764936353
455465.710642614693
455475.712201902701
455459.637885071163
455454.603568764112
455458.905910792993
455452.063287644181
455464.835137115675
455466.566020792641
...

result:

ok 1781 numbers

Test #21:

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

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.474486080755
284359.793732645165
284363.973878313380
284349.908226094150
284348.813509705709
284360.559810770326
284354.997431616939
284364.124745337409
284362.680004575581
284362.496790819510
64050.720210684500
284352.725997149013
284351.400949598872
284351.037832076836
284357.907791704172
2...

result:

ok 1781 numbers

Test #22:

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

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.621394643036
393120.744903681625
393130.189351588779
393123.058599690674
393128.134296897333
393119.033379073080
393131.716431363719
393123.275621858600
393117.288585386123
393128.219226072019
393128.297637329611
393121.165896118328
393113.829886579246
393115.189056911913
393125.098459256173
...

result:

ok 1781 numbers

Test #23:

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

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.935415039392
234686.780762982758
234696.224052096804
234689.234624189150
234681.509833541262
234688.325222284388
234690.985530420934
234685.314701468771
234697.883062973589
234685.983333384618
234683.342920964351
234692.978097465064
234686.076394613949
234686.240279400459
396836.114925302041
...

result:

ok 1781 numbers

Test #24:

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

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.446418637119
427613.185439975001
427604.196937802422
427623.368971969583
427607.133601538895
427612.816413233057
427615.354498480039
427597.853682650079
427608.729955872404
427602.786779337795
427604.037703262526
427604.612118823978
427612.180633454584
427618.994996686000
427621.963920057169
...

result:

ok 1781 numbers

Test #25:

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

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.916516885703
4368.075870665846
4363.002009875001
4351.157856369777
4369.071821570437
4360.810115602476
4359.496128618513
4364.152108232065
4372.291164919349
4363.808491637304
4356.865406077191
4360.211548211098
4362.496344194204
4358.764831637725
4357.229155238040
4358.931910459638
4358.0025208...

result:

ok 1781 numbers

Test #26:

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

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.603325437405
730974.082282885094
730965.485102324048
730979.792987545952
730970.738391330582
731000.140459052403
730970.309227254009
730996.557869047858
730961.615551213734
730976.590829609660
730959.800117169390
730979.528497912688
730970.644548550365
730971.744321334525
730991.901436980814
...

result:

ok 1781 numbers

Test #27:

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

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.206267791800
1169879.348474515136
372097.806162880734
372088.176890144998
372081.497990245640
372081.014669749246
372057.621846727037
372089.501738643099
372069.491004181677
372077.254180424730
372071.926200642949
372082.750912222604
372088.444027550926
372062.603239993041
372062.172322481056...

result:

ok 1781 numbers

Test #28:

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

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.073767740705
10.858474455994
7.649399947186
8.504961407320
9.384559030415
7.832875423537
1.442652097559
15.734226393396
16.866311506196
12.607900073843
21.791970094608
6.477587843636
6.175927845593
13.788203719122
8.175175157812
14.163884242599
18.257900167049
6.948376998709
9.517544937156
4.6494...

result:

ok 1781 numbers

Test #29:

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

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.000000000000
10.198039027186
12.428026557854
1330347.149796098238
8.235801547193
10.509797530053
11.666734691944
8.602325267043
15.567374401308
3.605551275464
19.209372712299
20.446364563637
7.211102550928
12.741394968782
12.384776310850
11.969333116916
8.931945694498
3.464101615138
8.54400374531...

result:

ok 1781 numbers

Test #30:

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

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.404020532762
20.388932589928
10.219556644124
20.925345696221
5.044131121937
12.248079206413
2.875484503403
2.688505513510
16.348661420395
12.647248742068
11.533394028769
1.363332334346
23.964433571521
2.724240537695
9.614741742517
6.293812489333
6.835165670830
7.690627985960
5.929336450028
7.35812...

result:

ok 1781 numbers

Test #31:

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

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.939891245093
7.636154837127
9.393240172864
10.382786181005
14.470323469725
7.063542469186
8.730376702242
24.092766949417
201368.836075977481
5.396905887552
9.106445034651
17.828815581801
24.470237133068
17.738001743309
11.399684533477
13.568083291459
18.694869081513
19.407960066178
17.46101057851...

result:

ok 1781 numbers

Test #32:

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

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.714502444978
25.436089213233
16.876295650954
26.164132134780
11.366678326338
31.200047260154
26.956622796969
25.934290539356
22.987666782371
28.222788078910
10.749026025142
5.699087522521
26.930796393891
21.336523649953
24.212014084985
25.574932048935
27.689547603965
1162982.790501752635
17.39208...

result:

ok 1781 numbers

Test #33:

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

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.120900293544
12.277227668503
25.756713381830
6.994111524609
23.982515970802
7.039216474162
11.851136292773
20.909023812565
16.751544388281
14.312981916307
15.172418208066
24.935797361358
17.093704927258
18.677130187407
14.734352280987
11.496295401678
2.530710130843
5.175208500927
14.126104661131
...

result:

ok 1781 numbers

Test #34:

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

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.932650869595
7.211102550928
5.000000000000
12.182294316343
18.000000000000
0.277402423779
12.933040773419
1024855.136242259527
12.419123557141
3.255764119220
5.663885030091
9.097817830700
16.056151469141
16.126983401557
4.538872557400
12.778779894090
11.461157540771
10.699635702053
4.123105625618...

result:

ok 1781 numbers

Test #35:

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

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.568753981684
25.129812639925
22.088197987948
19.749627068679
15.395332340873
17.104713491054
17.169552281294
13.350596104396
22.120516873341
22.166031461238
26.006095050953
12.796947706459
17.014458537400
18.166781274700
24.451764298294
23.176696895742
24.993967617269
0.992054701557
24.7959935250...

result:

ok 1781 numbers

Test #36:

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

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.236067977500
8.796002999432
15.697291772533
19.475761334388
9.055385138137
11.394671052405
5.099019513593
19.000000000000
8.619418339727
9.192525513532
16.672020795291
714191.239337195992
13.989425910523
2.652414037440
9.848857801796
16.267528012327
9.529380417477
2.708203932499
5.762470022539
15....

result:

ok 1781 numbers

Test #37:

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

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.977772290466
2.750120773895
0.846777708005
1.464071052924
0.585786437627

result:

ok 5 numbers

Test #38:

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

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.462488165066
15.750796763274
53.678242234964
82.368444069145
13.983800968931
37.949624407689
19.417382739503
26436.954804314388
16.276546051928
17.455115463883
41.139742618443
10.886385126363
2.541277018344
43.124079192333
91.936832738013
29490.058645599274
25443.538643692929
26521.917535813154
25...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 159ms
memory: 5884kb

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.972263364412
1395.006262689376
65837.716040132960
3799.085782635236
3433.758283839744
194.090692227504
7369.210725630252
265305.153138388821
8568.334302155668
4911.650769248730
54497.524328931977
3603.753680499819
3575.120818854322
159352.017849327909
3626.608676666327
100481.178871008728
7473...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 143ms
memory: 6316kb

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.636172539180
5614.804600055530
18063.491359815380
48666.350136998721
29146.202153789942
1712.932520099852
166623.047461909882
37945.226124340094
14861.689749269352
52982.283561519303
2858.978120407317
13281.349540431773
2313.817285228469
9696.146442923928
24522.006430963105
915.755264890945
111...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 105ms
memory: 6572kb

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.000000000000
7.000000000002
7.000000000002
7.000000000000
9.000000000000
9.000000000000
9.000000000000
9.000000000000
1.007620982403
2.000000000000
11.401762144591
11.401754250991
8.006305499964
9.000010000100
9.000000000000
20.124611797498
0.110770276275
2.000000000000
19.313217235966
19.31320791...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 200ms
memory: 7072kb

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.869296048307
10.547084101735
20.338245462572
11.047239177453
29307.643746329024
8.696939181899
12.982205241010
42.208825685674
18.284846836505
1.324501422794
89248.113329288419
10.698730257678
12.063924232612
82.456790890416
0.273929450747
4.082102156985
229619.295449568366
173821.018307629594
20....

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 198ms
memory: 6560kb

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.618140549166
10.735444517649
2.729671499258
305762.777518170187
18.130777790009
24.254768209419
9.750601630259
7.181199237389
9.185528209802
51.864042051995
57.784192180165
304131.586405272188
91.131096195532
21.511942220704
5.610489981997
13.296642826366
149597.310050028784
6.007465005420
13...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 192ms
memory: 6624kb

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.040233125657
17.842584580622
17.075114544293
11.280952583045
219404.306297076982
27.077625533554
228139.775011337741
14.189689595232
32.151684768992
13.958807258866
30.474901571748
352634.110645619105
220634.768760059378
67.337972452478
65.610884685283
7.954646926934
8.880469192908
24.576646088752...

result:

ok 100000 numbers