QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563992#3854. RadarFortitude#AC ✓139ms5944kbC++231.8kb2024-09-14 18:26:462024-09-14 18:26:46

Judging History

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

  • [2024-09-14 18:26:46]
  • 评测
  • 测评结果:AC
  • 用时:139ms
  • 内存:5944kb
  • [2024-09-14 18:26:46]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using ld = long double;

template<class T> struct Point{
	T x, y;
	Point(T x = 0, T y = 0): x(x), y(y) {}
	using P = Point;
	P operator + (P p) const { return P(x + p.x, y + p.y); }
	P operator - (P p) const { return P(x - p.x, y - p.y); }
	P operator * (T d) const { return P(x * d, y * d); }
	P operator / (T d) const { return P(x / d, y / d); }
	bool side() const {
		if(y == 0) return x < 0;
		return y < 0;
	}
	T cross(P p) const { return x * p.y - y * p.x; }
	bool operator < (P p) const {
		if(side() == p.side()) return cross(p) > 0;
		return p.side();
	}
	T dot(P p) const { return x * p.x + y * p.y; }
	T dist2() const { return dot(*this); }
	ld dist() const { return sqrtl(dist2()); }
	P unit() const { return *this / dist(); }
};
using P = Point<ll>;
using Pld = Point<ld>;
const int N = 1e5;

int n, m, R[N];
P a[N];

ld solve(int pos, Pld p){
	Pld v{a[pos].x, a[pos].y};
	v = v.unit();
	int tl = -1, tr = n;
	while(tr - tl > 1){
		int tm = tl + tr >> 1;
		if((p - v * R[tm]).dot(v) < 0) tr = tm;
		else tl = tm;
	}
	ld res = 1e18;
	if(tl >= 0) res = min(res, (p - v * R[tl]).dist());
	if(tr < n) res = min(res, (p - v * R[tr]).dist());
	return res;
}

main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin >> n >> m >> q;
	for(int i = 0; i < n; i++) cin >> R[i];
	sort(R, R + n);
	for(int i = 0; i < m; i++) cin >> a[i].x >> a[i].y;
	sort(a, a + m);
	for(P p; q--;){
		cin >> p.x >> p.y;
		int i = upper_bound(a, a + m, p) - a;
		ld ans = solve(i % m, Pld{p.x, p.y});
		i = (i + m - 1) % m;
		ans = min(ans, solve(i, Pld{p.x, p.y}));
		cout << fixed << setprecision(9) << ans << '\n';
	}
}

詳細信息

Test #1:

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

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.605291073
0.977772290
1.551845105
1.414213562

result:

ok 4 numbers

Test #2:

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

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.874985099
15.874985099
15.874985099
15.874985099
15.874985099
15.874985099
15.874985099
15.874985099
4.929656701
4.929656701
4.929656701
4.929656701
4.929656701
4.929656701
4.929656701
4.929656701
2.000000000
2.000000000
2.000000000
2.000000000
0.071067812
0.071067812
0.071067812
0.071067812
2.00...

result:

ok 32 numbers

Test #3:

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

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.055385138
4.123105626
3.605551275
11.045361017
15.297058541
1.414213562
8.246211251
7.000000000
8.944271910
3.000000000
12.165525061
5.000000000
5.099019514
11.180339887
1.414213562
2.000000000
2.000000000
3.000000000
3.162277660
8.246211251
4.472135955
5.000000000
8.544003745
9.000000000
19.41648...

result:

ok 1681 numbers

Test #4:

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

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.777372119
4.631593683
6.895656101
12.291422905
6.555964004
4.270304206
4.392536000
6.367825886
6.555964004
2.990316379
10.187520359
2.833626167
2.977064831
4.696779860
4.352239889
11.328455810
3.384030148
1.836459366
2.947251516
7.635131896
9.092184670
8.026974776
5.727556814
10.738462416
2.67892...

result:

ok 1681 numbers

Test #5:

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

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.000000000
4.000000000
4.000000000
4.000000000
5.000000000
5.000000000
5.000000000
5.000000000
1.000000000
1.000000000
1.000000000
1.000000000
8.062257748
8.062257748
8.062257748
8.062257748

result:

ok 16 numbers

Test #6:

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

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.000000000
2.000000000
4.000000000
8.000000000
16.000000000
32.000000000
64.000000000
128.000000000
256.000000000
512.000000000
1024.000000000
2048.000000000
4096.000000000
8192.000000000
16384.000000000
32768.000000000
65536.000000000
131072.000000000
262144.000000000
524288.000000000
1047.0004775...

result:

ok 120 numbers

Test #7:

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

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.393071596
16.453441243
14.475640085
19.043231368
16.182932417
19.043231368
19.010576537
3.305893554
11.763187621
14.667308360
16.295525640
7.617705511
16.692652903
25.870057685
16.182932199
20.084870432
10.694511685
19.295116007
23.759261885
19.336165639
17.384776311
6.424334549
18.105696170
15.61...

result:

ok 1681 numbers

Test #8:

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

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.000000000
3.000000000
2.000000000
1.000000000
0.000000000
1.000000000
2.000000000
1.000000000
0.000000000
1.000000000
2.000000000
3.000000000
4.000000000
3.000000000
2.000000000
1.000000000
0.000000000
1.000000000
2.000000000
3.000000000
4.000000000
3.000000000
2.000000000
1.000000000
0.000000000
...

result:

ok 108 numbers

Test #9:

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

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.219544457
3.162277660
15.033296378
6.708203932
6.000000000
19.104973175
12.000000000
1.000000000
5.656854249
4.123105626
1.414213562
5.099019514
12.369316877
19.235384062
6.000000000
9.486832981
6.324555320
4.123105626
18.027756377
4.472135955
13.341664064
2.236067977
13.152946438
7.071067812
7.28...

result:

ok 1681 numbers

Test #10:

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

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.414213562
18.439088915
4.472135955
12.041594579
14.317821063
10.440306509
19.026297590
15.033296378
3.605551275
8.544003745
18.027756377
17.464249197
20.000000000
5.000000000
13.341664064
10.049875621
18.027756377
16.000000000
1.414213562
19.104973175
17.000000000
12.165525061
10.049875621
9.84885...

result:

ok 1681 numbers

Test #11:

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

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.341667966
7.615773106
19.235399882
17.262680445
14.142135624
18.027764373
10.198046880
11.704699911
6.000000000
16.031219542
14.035676835
3.000000000
7.280125289
20.099751242
14.142139587
13.000000000
16.278804854
4.472135955
8.944271910
5.000000000
2.000000000
18.248287591
15.524174696
4.9999903...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.071067812

result:

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

Test #13:

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

input:

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

output:

7.071066821

result:

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

Test #14:

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

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.000000000
0.000000000
1.000000000
0.000000000
1.000000000
2.000000000
1.000000000
0.000000000
1.000000000
2.000000000
3.000000000
4.000000000
5.000000000
6.000000000
7.000000000
8.000000000
9.000000000
10.000000000
1.414213562
2.236067977
3.162277660
4.123105626
5.099019514
6.082762530
7.071067812...

result:

ok 36 numbers

Test #15:

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

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.318273190
3.147379239
3.043003665
5.601139658
6.294758478
6.553438497
6.086007329
7.480164533

result:

ok 8 numbers

Test #16:

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

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.998865702
14.525423019
21.073102118
31.843189113
115.924895014
49.991391055
60.506629716
69.958130040
134.902308151
90.172561431
100.220151412
110.154852885
119.838138058
169.259259925
139.857713810
149.903862612
159.813034019
169.924008913
209.997050922
189.713651035
199.622975023
209.788572656
...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 116ms
memory: 5944kb

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.000000000
15.295841309
21.472081503
30.839308520
35.006555273
50.931458107
60.506619829
70.363795442
80.007038937
90.056171322
100.000633293
110.050508280
119.838128086
129.885197989
134.868076476
149.833874636
159.950469677
169.923998940
174.785455207
189.629416254
199.660469855
209.738565800
21...

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 111ms
memory: 5840kb

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.000000000
11.793537329
15.006851569
30.316874089
40.113906821
50.140933717
60.175584315
70.363795442
80.125534801
89.856351460
100.000633293
109.955169614
119.767282241
129.812131979
139.932670847
149.713860057
159.753646615
169.738741225
179.900467152
189.818902378
194.756858677
209.843313163
21...

result:

ok 99999 numbers

Test #19:

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

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.248114477
1548.728110912
1574.070850192
1568.855156610
1558.582578139
1562.014764099
1556.584271779
1558.564638008
1566.850548158
1566.948507824
1544.539412209
1556.455197784
1555.182232268
1562.699966582
1569.163895395
1561.121016860
1545.521680095
1543.064681817
1557.134246845
1564.84673773...

result:

ok 1781 numbers

Test #20:

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

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.068343449
455444.037305271
455456.306609651
455477.370048754
455453.183515038
455440.187062229
455465.030764936
455465.710642615
455475.712201903
455459.637885071
455454.603568764
455458.905910793
455452.063287644
455464.835137116
455466.566020793
455472.106707416
455449.822857526
455444.3022...

result:

ok 1781 numbers

Test #21:

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

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.474486081
284359.793732645
284363.973878313
284349.908226094
284348.813509706
284360.559810770
284354.997431617
284364.124745337
284362.680004576
284362.496790819
64050.720210685
284352.725997149
284351.400949599
284351.037832077
284357.907791704
284361.143620402
284357.184700945
284366.54186...

result:

ok 1781 numbers

Test #22:

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

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.621394643
393120.744903682
393130.189351589
393123.058599691
393128.134296897
393119.033379073
393131.716431364
393123.275621859
393117.288585386
393128.219226072
393128.297637330
393121.165896118
393113.829886579
393115.189056912
393125.098459256
393130.383054930
393119.661164347
393125.9189...

result:

ok 1781 numbers

Test #23:

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

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.935415039
234686.780762983
234696.224052097
234689.234624189
234681.509833541
234688.325222284
234690.985530421
234685.314701469
234697.883062974
234685.983333385
234683.342920964
234692.978097465
234686.076394614
234686.240279400
396836.114925302
313138.097860579
234682.101298000
234696.2927...

result:

ok 1781 numbers

Test #24:

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

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.446418637
427613.185439975
427604.196937802
427623.368971970
427607.133601539
427612.816413233
427615.354498480
427597.853682650
427608.729955872
427602.786779338
427604.037703263
427604.612118824
427612.180633455
427618.994996686
427621.963920057
427601.410370603
427606.962712487
427626.1253...

result:

ok 1781 numbers

Test #25:

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

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.916516886
4368.075870666
4363.002009875
4351.157856370
4369.071821570
4360.810115602
4359.496128619
4364.152108232
4372.291164919
4363.808491637
4356.865406077
4360.211548211
4362.496344194
4358.764831638
4357.229155238
4358.931910460
4358.002520899
546468.250839959
4358.102921692
4360.01941740...

result:

ok 1781 numbers

Test #26:

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

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.603325437
730974.082282885
730965.485102324
730979.792987546
730970.738391331
731000.140459052
730970.309227254
730996.557869048
730961.615551214
730976.590829610
730959.800117169
730979.528497913
730970.644548550
730971.744321335
730991.901436981
730983.230418933
832464.818839349
730992.4496...

result:

ok 1781 numbers

Test #27:

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

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.206267792
1169879.348474515
372097.806162881
372088.176890145
372081.497990246
372081.014669749
372057.621846727
372089.501738643
372069.491004182
372077.254180425
372071.926200643
372082.750912223
372088.444027551
372062.603239993
372062.172322481
372088.065690161
372082.013262062
372086.230...

result:

ok 1781 numbers

Test #28:

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

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.073767741
10.858474456
7.649399947
8.504961407
9.384559030
7.832875424
1.442652098
15.734226393
16.866311506
12.607900074
21.791970095
6.477587844
6.175927846
13.788203719
8.175175158
14.163884243
18.257900167
6.948376999
9.517544937
4.649449527
12.849949194
9.204736046
22.853322379
7.177937007
7...

result:

ok 1781 numbers

Test #29:

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

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.000000000
10.198039027
12.428026558
1330347.149796098
8.235801547
10.509797530
11.666734692
8.602325267
15.567374401
3.605551275
19.209372712
20.446364564
7.211102551
12.741394969
12.384776311
11.969333117
8.931945694
3.464101615
8.544003745
398065.761457791
14.146298067
12.041594579
11.966873475...

result:

ok 1781 numbers

Test #30:

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

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.404020533
20.388932590
10.219556644
20.925345696
5.044131122
12.248079206
2.875484503
2.688505514
16.348661420
12.647248742
11.533394029
1.363332334
23.964433572
2.724240538
9.614741743
6.293812489
6.835165671
7.690627986
5.929336450
7.358122898
5.549414569
3.071702038
19.269418579
2.249309801
1.3...

result:

ok 1781 numbers

Test #31:

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

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.939891245
7.636154837
9.393240173
10.382786181
14.470323470
7.063542469
8.730376702
24.092766949
201368.836075977
5.396905888
9.106445035
17.828815582
24.470237133
17.738001743
11.399684533
13.568083291
18.694869082
19.407960066
17.461010579
11.636311482
18.956524222
8.989673609
10.547271858
21.3...

result:

ok 1781 numbers

Test #32:

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

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.714502445
25.436089213
16.876295651
26.164132135
11.366678326
31.200047260
26.956622797
25.934290539
22.987666782
28.222788079
10.749026025
5.699087523
26.930796394
21.336523650
24.212014085
25.574932049
27.689547604
1162982.790501753
17.392086162
11.680025780
7.975480035
15.185448752
7.469529063...

result:

ok 1781 numbers

Test #33:

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

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.120900294
12.277227669
25.756713382
6.994111525
23.982515971
7.039216474
11.851136293
20.909023813
16.751544388
14.312981916
15.172418208
24.935797361
17.093704927
18.677130187
14.734352281
11.496295402
2.530710131
5.175208501
14.126104661
14.087872962
26.086860855
19.541179997
14.980261327
11.74...

result:

ok 1781 numbers

Test #34:

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

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.932650870
7.211102551
5.000000000
12.182294316
18.000000000
0.277402424
12.933040773
1024855.136242260
12.419123557
3.255764119
5.663885030
9.097817831
16.056151469
16.126983402
4.538872557
12.778779894
11.461157541
10.699635702
4.123105626
18.574267045
11.907980517
0.726298733
1.485420634
16.492...

result:

ok 1781 numbers

Test #35:

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

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.568753982
25.129812640
22.088197988
19.749627069
15.395332341
17.104713491
17.169552281
13.350596104
22.120516873
22.166031461
26.006095051
12.796947706
17.014458537
18.166781275
24.451764298
23.176696896
24.993967617
0.992054702
24.795993525
17.808962225
16.787186779
752464.594215173
17.13439888...

result:

ok 1781 numbers

Test #36:

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

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.236067977
8.796002999
15.697291773
19.475761334
9.055385138
11.394671052
5.099019514
19.000000000
8.619418340
9.192525514
16.672020795
714191.239337196
13.989425911
2.652414037
9.848857802
16.267528012
9.529380417
2.708203932
5.762470023
15.364589173
9.099950063
2.152316806
446893.448894700
20.577...

result:

ok 1781 numbers

Test #37:

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

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.977772290
2.750120774
0.846777708
1.464071053
0.585786438

result:

ok 5 numbers

Test #38:

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

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.462488165
15.750796763
53.678242235
82.368444069
13.983800969
37.949624408
19.417382740
26436.954804314
16.276546052
17.455115464
41.139742618
10.886385127
2.541277019
43.124079192
91.936832738
29490.058645599
25443.538643693
26521.917535813
25.703495928
22.209882218
21.229329655
36.804742793
1142...

result:

ok 100 numbers

Test #39:

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

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.972263364
1395.006262689
65837.716040133
3799.085782635
3433.758283840
194.090692227
7369.210725630
265305.153138389
8568.334302156
4911.650769249
54497.524328932
3603.753680500
3575.120818854
159352.017849328
3626.608676666
100481.178871009
74738.612382726
2868.239125314
3345.947195781
3533.4...

result:

ok 100000 numbers

Test #40:

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

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.636172539
5614.804600056
18063.491359816
48666.350136999
29146.202153790
1712.932520100
166623.047461910
37945.226124340
14861.689749269
52982.283561520
2858.978120408
13281.349540432
2313.817285229
9696.146442924
24522.006430963
915.755264891
11130.988761338
94958.556365763
12364.170802470
177...

result:

ok 100000 numbers

Test #41:

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

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.000000000
7.000000000
7.000000000
7.000000000
9.000000000
9.000000000
9.000000000
9.000000000
1.007620982
2.000000000
11.401762145
11.401754251
8.006305500
9.000010000
9.000000000
20.124611797
0.110770276
2.000000000
19.313217236
19.313207916
16.012611000
18.000020000
18.000000000
32.449961479
0.5...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 138ms
memory: 5876kb

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.869296048
10.547084102
20.338245463
11.047239177
29307.643746329
8.696939183
12.982205241
42.208825686
18.284846837
1.324501423
89248.113329288
10.698730258
12.063924233
82.456790891
0.273929451
4.082102157
229619.295449568
173821.018307630
20.916145415
1.883300585
23.055221489
8.308814933
46457.5...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 139ms
memory: 5868kb

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.618140549
10.735444518
2.729671499
305762.777518170
18.130777790
24.254768209
9.750601630
7.181199237
9.185528211
51.864042052
57.784192180
304131.586405272
91.131096196
21.511942220
5.610489982
13.296642826
149597.310050029
6.007465006
13.378959490
6.608820142
16.792704044
5489.829402934
8.3...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 139ms
memory: 5816kb

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.040233126
17.842584581
17.075114544
11.280952583
219404.306297077
27.077625534
228139.775011338
14.189689595
32.151684770
13.958807259
30.474901573
352634.110645619
220634.768760059
67.337972453
65.610884685
7.954646927
8.880469193
24.576646089
25.157655052
10.979363371
20.528994110
50.011926830
2...

result:

ok 100000 numbers