QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253333#3854. Radaroogerbooger#AC ✓154ms9768kbC++144.1kb2023-11-16 21:34:372023-11-16 21:34:38

Judging History

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

  • [2023-11-16 21:34:38]
  • 评测
  • 测评结果:AC
  • 用时:154ms
  • 内存:9768kb
  • [2023-11-16 21:34:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int INF = 1e7;

struct Point {
	int x, y, id; // jak id < 0 tzn, że jestem pałągiem
};

ll scalar(Point a, Point b) {
	return a.x * 1LL * b.x + a.y * 1LL * b.y;
}

ld len(Point a) {
	return (ld)sqrt((ld)scalar(a, a));
}

ll det(Point a, Point b) {
	return a.x * 1LL *  b.y - a.y * 1LL * b.x;
}

ld dl_rzutu_a_na_b(Point a, Point b) {
	return (ld)scalar(a, b) / len(b);
}

int32_t main() {
	ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);

	int R, F, N;	cin >> R >> F >> N;
	vector<int> radii(R + 2, 0);
	for (int i = 1; i <= R; i++) {
		cin >> radii[i];
	}
	radii[R + 1] = INF;
	sort(begin(radii), end(radii));
	vector<Point> all_pts(F + N), pts(N), paly(F);
	for (int i = 0; i < F; i++) {
		int fx, fy;	cin >> fx >> fy;
		all_pts[i] = {fx, fy, -(i + 1)};
		paly[i] = all_pts[i];
	}
	for (int i = 0; i < N; i++) {
		int x, y;	cin >> x >> y;
		all_pts[i + F] = {x, y, (i + 1)};
		pts[i] = all_pts[i + F];
	}
	auto pom = [&](Point p) {
		if (p.x >= 0 && p.y == 0) return 0; // na prawej półprostej
		if (p.y > 0) return 1; // na górnym półokregu
		if (p.x < 0 && p.y == 0) return 2; // na lewej półprostej
		return 3; // na dole
	};
	int pom_a, pom_b; // zmienne pomocnicze
	auto cmp = [&](Point a, Point b) {
		pom_a = pom(a), pom_b = pom(b);
		if (pom_a != pom_b) return pom_a < pom_b;
		if (det(a, b) == 0) return a.id < b.id; // lz więc porównuję id
		return det(a, b) >= 0; 
	};
	sort(all_pts.begin(), all_pts.end(), cmp);

	vector<int> Left(N), Right(N);

	int M = N + F;

	int it = 0;
	while (all_pts[it].id > 0) it = (it - 1 + M) % M;
	int pre_left = all_pts[it].id;
	for (int i = 0; i < F + N; i++) {
		if (all_pts[i].id < 0) pre_left = all_pts[i].id;
		else {
			Left[all_pts[i].id - 1] = pre_left;
		}
	}
	it = M - 1;
	while (all_pts[it].id > 0) it = (it + 1) % M;
	int pre_right = all_pts[it].id;
	for (int i = F + N - 1; i >= 0; i--) {
		if (all_pts[i].id < 0) pre_right = all_pts[i].id;
		else {
			Right[all_pts[i].id - 1] = pre_right;
		}
	}
	cout << fixed << setprecision(15);
	auto cur_mini = [&](int i, int idx) {
		ld mini = INF;
		ld rzut = dl_rzutu_a_na_b(pts[i], paly[idx]);
		it = int(upper_bound(begin(radii), end(radii), rzut) - begin(radii));
		ld alfa = atan2(paly[idx].y,paly[idx].x);
		if(it == 0) it++;
		if(it > 0 && it < R+1) {
			int r = radii[it];
			ld ax = (ld)cos(alfa)*r, ay = (ld)sin(alfa)*r;
			mini = min(mini, sqrt((ax-pts[i].x)*(ax-pts[i].x)+(ay-pts[i].y)*(ay-pts[i].y) ));
		}
		it--;
		if(it > 0 && it < R+1) {
			int r = radii[it];
			ld ax = (ld)cos(alfa)*r, ay = (ld)sin(alfa)*r;
			mini = min(mini, sqrt((ax-pts[i].x)*(ax-pts[i].x)+(ay-pts[i].y)*(ay-pts[i].y) ));
		}
		return mini;
	};
	for (int i = 0; i < N; i++) {
		ld mini = cur_mini(i, -Left[i]-1);
		ld mini2 = cur_mini(i, -Right[i]-1);
		cout << min(mini, mini2) << "\n";
	}


	return 0;
}

详细

Test #1:

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

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.551845105401789
1.414213562373095

result:

ok 4 numbers

Test #2:

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

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: 4188kb

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.055385138137418
4.123105625617661
3.605551275463989
11.045361017187262
15.297058540778354
1.414213562373094
8.246211251235322
7.000000000000001
8.944271909999160
3.000000000000002
12.165525060596438
5.000000000000000
5.099019513592785
11.180339887498947
1.414213562373095
2.000000000000000
2.000000...

result:

ok 1681 numbers

Test #4:

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

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.895656100977255
12.291422905366940
6.555964003580544
4.270304206047021
4.392536000447645
6.367825885745279
6.555964003580545
2.990316379370500
10.187520359495127
2.833626166508712
2.977064831365350
4.696779860161955
4.352239888693121
11.328455809796768
3.384030...

result:

ok 1681 numbers

Test #5:

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

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
4.999999999999999
5.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
8.062257748298549
8.062257748298549
8.062257748298549
8.062257748298550

result:

ok 16 numbers

Test #6:

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

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
7.999999999999999
15.999999999999998
31.999999999999996
63.999999999999992
127.999999999999984
255.999999999999969
511.999999999999937
1023.999999999999875
2047.999999999999749
4095.999999999999498
8191.999999999998997
16383.999999999997994
32767...

result:

ok 120 numbers

Test #7:

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

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.475640085235757
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: 0ms
memory: 4148kb

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: 4192kb

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.162277660168381
15.033296378372908
6.708203932499371
6.000000000000001
19.104973174542800
12.000000000000001
1.000000000000000
5.656854249492380
4.123105625617660
1.414213562373096
5.099019513592784
12.369316876852981
19.235384061671344
5.999999999999999
9.486832980505139
6.32455...

result:

ok 1681 numbers

Test #10:

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

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.414213562373096
18.439088914585775
4.472135954999579
12.041594578792295
14.317821063276354
10.440306508910551
19.026297590440449
15.033296378372909
3.605551275463989
8.544003745317532
18.027756377319947
17.464249196572981
20.000000000000001
4.999999999999999
13.341664064126335
10.049875621120890
1...

result:

ok 1681 numbers

Test #11:

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

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.615773105863909
19.235399881681894
17.262680444705100
14.142135623730951
18.027764372990675
10.198046879676520
11.704699910719624
5.999999999999999
16.031219541881398
14.035676835267186
3.000000000000000
7.280125289047177
20.099751242241781
14.142139587489014
12.999999999999999
...

result:

ok 1681 numbers

Test #12:

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

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: 4232kb

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: 3976kb

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: 4216kb

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: 121ms
memory: 9380kb

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.525423018761118
21.073102117794252
31.843189113241069
115.924895013615673
49.991391054939895
60.506629716441606
69.958130039585847
134.902308151242213
90.172561431422951
100.220151411668209
110.154852885070048
119.838138057650305
169.259259924830495
139.857713809972361
149.9038...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 121ms
memory: 9524kb

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: 125ms
memory: 9428kb

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.006851569378937
30.316874089052132
40.113906820859333
50.140933717450125
60.175584315259197
70.363795442201724
80.125534801392464
89.856351459773306
100.000633293051918
109.955169614314124
119.767282240876358
129.812131979221723
139.932670846875565
149.713860...

result:

ok 99999 numbers

Test #19:

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

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.248114476979822
1548.728110911664889
1574.070850191947784
1568.855156609634848
1558.582578139035295
1562.014764098693465
1556.584271779073085
1558.564638007550465
1566.850548158155619
1566.948507823863285
1544.539412209167181
1556.455197783836330
1555.182232268123369
1562.699966582056269
1569...

result:

ok 1781 numbers

Test #20:

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

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.370048753881264
455453.183515037673487
455440.187062228541151
455465.030764936369224
455465.710642614713265
455475.712201902747296
455459.637885071202504
455454.603568764108644
455458.905910793023452
455452.063287644227330
4...

result:

ok 1781 numbers

Test #21:

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

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.813509705685959
284360.559810770306200
284354.997431616959659
284364.124745337440004
284362.680004575557234
284362.496790819477155
64050.720210684621033
284352.725997149006645
284351.400949598880203
28...

result:

ok 1781 numbers

Test #22:

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

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.621394643047012
393120.744903681625544
393130.189351588748224
393123.058599690699737
393128.134296897345280
393119.033379073073178
393131.716431363734984
393123.275621858658752
393117.288585386112459
393128.219226072018586
393128.297637329649206
393121.165896118341834
393113.829886579257362
3...

result:

ok 1781 numbers

Test #23:

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

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.234624189158282
234681.509833541270240
234688.325222284388957
234690.985530420926125
234685.314701468789096
234697.883062973601724
234685.983333384637376
234683.342920964368872
234692.978097465063811
234686.076394613965178
2...

result:

ok 1781 numbers

Test #24:

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

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.185439975044517
427604.196937802469591
427623.368971969593105
427607.133601538887405
427612.816413233068744
427615.354498480043617
427597.853682650099557
427608.729955872431020
427602.786779337812050
427604.037703262545961
427604.612118823957161
427612.180633454641395
4...

result:

ok 1781 numbers

Test #25:

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

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.157856369776464
4369.071821570437296
4360.810115602476068
4359.496128618513618
4364.152108232064847
4372.291164919348959
4363.808491637303432
4356.865406077191372
4360.211548211098618
4362.496344194203423
4358.764831637725666
4357.2...

result:

ok 1781 numbers

Test #26:

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

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.738391330580782
731000.140459052441713
730970.309227254064524
730996.557869047915290
730961.615551213763922
730976.590829609719606
730959.800117169367127
730979.528497912748151
730970.644548550406398
7...

result:

ok 1781 numbers

Test #27:

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

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.206267791915138
1169879.348474515185671
372097.806162880731449
372088.176890145037078
372081.497990245673208
372081.014669749227465
372057.621846727057147
372089.501738643153857
372069.491004181666568
372077.254180424742515
372071.926200642954370
372082.750912222626368
372088.444027550949443
...

result:

ok 1781 numbers

Test #28:

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

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.649399947186103
8.504961407320144
9.384559030414698
7.832875423536831
1.442652097559291
15.734226393396022
16.866311506195664
12.607900073843284
21.791970094608371
6.477587843635738
6.175927845593418
13.788203719122256
8.175175157812430
14.163884242599090
18.2...

result:

ok 1781 numbers

Test #29:

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

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: 4300kb

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.219556644123651
20.925345696220928
5.044131121936667
12.248079206413251
2.875484503402901
2.688505513510126
16.348661420395246
12.647248742068139
11.533394028768593
1.363332334345770
23.964433571521225
2.724240537695449
9.614741742516544
6.293812489332658
6.83...

result:

ok 1781 numbers

Test #31:

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

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: 4284kb

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.436089213233455
16.876295650953959
26.164132134780406
11.366678326338351
31.200047260154136
26.956622796969487
25.934290539356099
22.987666782370989
28.222788078910079
10.749026025142498
5.699087522521475
26.930796393891078
21.336523649952786
24.212014084984916
25.5749320489346...

result:

ok 1781 numbers

Test #33:

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

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: 4260kb

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.933040773418724
1024855.136242259555956
12.419123557141262
3.255764119219941
5.663885030090966
9.097817830699936
16.056151469141041
16.126983401556800
4.538872557399927
12.77877989409033...

result:

ok 1781 numbers

Test #35:

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

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: 4184kb

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.796002999431881
15.697291772532746
19.475761334387566
9.055385138137417
11.394671052404843
5.099019513592785
19.000000000000000
8.619418339727374
9.192525513532268
16.672020795290663
714191.239337196014560
13.989425910523265
2.652414037440156
9.848857801796105
16.267528012327284
...

result:

ok 1781 numbers

Test #37:

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

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.846777708005353
1.464071052923670
0.585786437626905

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 34ms
memory: 5908kb

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.462488164976752
15.750796763295397
53.678242234958857
82.368444069323251
13.983800968719680
37.949624407761928
19.417382739923074
26436.954804314449554
16.276546052035156
17.455115463843979
41.139742618381720
10.886385126892901
2.541277018721269
43.124079192311023
91.936832737977863
29490.05864559...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 136ms
memory: 9052kb

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.972263364388617
1395.006262689433449
65837.716040132988184
3799.085782635251394
3433.758283839787144
194.090692227498735
7369.210725630295098
265305.153138388887044
8568.334302155730533
4911.650769248802638
54497.524328931921286
3603.753680499854907
3575.120818854348499
159352.017849327979363
...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 135ms
memory: 7096kb

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.636172539122682
5614.804600055690309
18063.491359815855935
48666.350136998678149
29146.202153790187078
1712.932520099804184
166623.047461909966415
37945.226124340093218
14861.689749269334217
52982.283561519536576
2858.978120407589267
13281.349540431638649
2313.817285228479159
9696.1464429239267...

result:

ok 100000 numbers

Test #41:

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

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.401762144590731
11.401754250991380
8.006305499963675
9.000010000100001
9.000000000000000
20.124611797498107
0.1107702...

result:

ok 99999 numbers

Test #42:

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

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.869296048232868
10.547084101731354
20.338245462781244
11.047239177446859
29307.643746329082010
8.696939182854458
12.982205241129170
42.208825685673212
18.284846836658076
1.324501422810708
89248.113329288446813
10.698730258109753
12.063924232544237
82.456790890808939
0.273929450537330
4.08210215696...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 154ms
memory: 9672kb

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.735444517532444
2.729671499241095
305762.777518170212318
18.130777790224439
24.254768209496876
9.750601630231078
7.181199237318590
9.185528210672959
51.864042052024183
57.784192180361271
304131.586405272125631
91.131096195726832
21.511942220493922
5.610489981860064
13.29664...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 154ms
memory: 9756kb

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.040233125600037
17.842584580829165
17.075114544373796
11.280952583053945
219404.306297076978026
27.077625533552654
228139.775011337773975
14.189689595213452
32.151684769638619
13.958807259080431
30.474901572741015
352634.110645619148073
220634.768760059418099
67.337972452780573
65.610884685282383
...

result:

ok 100000 numbers