QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197878#3854. RadarForever_Young#AC ✓145ms6260kbC++142.0kb2023-10-02 21:10:032023-10-02 21:10:03

Judging History

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

  • [2023-10-02 21:10:03]
  • 评测
  • 测评结果:AC
  • 用时:145ms
  • 内存:6260kb
  • [2023-10-02 21:10:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long double D;
typedef pair<int, int> pii;
typedef long long LL;
const int N = 100011;
const D pi = acos((D)-1.);
struct P {
	D x, y;
	void scan() {
		double _x, _y;
		scanf("%lf%lf", &_x, &_y);
		x = _x; y = _y;
	}
	D atan2() const {
		return ::atan2(	y, x);
	}
	D sqrlen() const {
		return x * x + y * y;
	}
	D len() const {
		return sqrt(sqrlen());
	}
	P operator - (const P & b) const {
		return P{x - b.x, y - b.y};
	}
	P operator + (const P & b) const {
		return P{x + b.x, y + b.y};
	}
	D operator % (const P & b) const {
		return x * b.x + y * b.y;
	}
	D operator * (const P & b) const {
		return x * b.y - y * b.x;
	}
	void print() const {
		printf("%.12f %.12f\n", (double)x, (double)y);
	}
	P rev() const {
		return P{-y, x};
	}
};
P operator * (const D & x, const P & b) {
	return P{x * b.x, x * b.y};
}
struct L {
	P s, d;
};
P intersect(const L & a, const L & b) {
	D lambda = (b.s - a.s) * b.d / (a.d * b.d);
	return a.s + lambda * a.d;
}
int d[N];
D a[N];
int main() {
	int r, f, n;
	scanf("%d%d%d", &r, &f, &n);
	for(int i = 1; i <= r; i++) {
		scanf("%d", &d[i]);
	}
	sort(d + 1, d + r + 1);
	d[r + 1] = d[r];
	d[0] = d[1];
	for(int i = 1; i <= f; i++) {
		P x;
		x.scan();
		a[i] = x.atan2();
	}
	sort(a + 1, a + 1 + f);
	a[f + 1] = a[1] + 2 * pi;
	a[0] = a[f] - 2 * pi;
	for(int i = 0; i < n; i++) {
		P x;
		x.scan();
		D ang = x.atan2();
		D ans = 1e50;
		int k = lower_bound(a + 1, a + f + 1, ang) - a;
		for(int k1 = 0; k1 < 2; k1++) {
			P dir{cos(a[k - k1]), sin(a[k - k1])};
			P p = intersect({{0, 0}, dir}, {x, dir.rev()});
			D dis = p % dir;
			int j = lower_bound(d + 1, d + r + 1, dis) - d;
			for(int j1 = 0; j1 < 2; j1++) {
				P p{d[j - j1] * cos(a[k - k1]), d[j - j1] * sin(a[k - k1])};
				//p.print();
				//x.print();
				ans = min(ans, (p - x).len());
			}
		}
		printf("%.20f\n", (double)ans);
	}

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107291663997170
0.97777229046560498738
1.55184510540178899340
1.41421356237309514547

result:

ok 4 numbers

Test #2:

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

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.87498509925757517181
15.87498509925757517181
15.87498509925757517181
15.87498509925757517181
15.87498509925757517181
15.87498509925757517181
15.87498509925757517181
15.87498509925757517181
4.92965670104572328825
4.92965670104572328825
4.92965670104572328825
4.92965670104572328825
4.92965670104572...

result:

ok 32 numbers

Test #3:

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

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.05538513813741730019
4.12310562561766058565
3.60555127546398868077
11.04536101718726115450
15.29705854077835347482
1.41421356237309425730
8.24621125123532117129
7.00000000000000088818
8.94427190999915922021
3.00000000000000177636
12.16552506059643867786
5.00000000000000000000
5.0990195135927844916...

result:

ok 1681 numbers

Test #4:

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

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.77737211930355165634
4.63159368259021420045
6.89565610097725567584
12.29142290536693948866
6.55596400358054420821
4.27030420604702154463
4.39253600044764525023
6.36782588574527874670
6.55596400358054420821
2.99031637937050032150
10.18752035949512801949
2.83362616650871190771
2.9770648313653502725...

result:

ok 1681 numbers

Test #5:

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

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.00000000000000000000
4.00000000000000000000
4.00000000000000000000
4.00000000000000000000
5.00000000000000000000
5.00000000000000000000
4.99999999999999911182
5.00000000000000000000
1.00000000000000000000
1.00000000000000000000
1.00000000000000000000
1.00000000000000000000
8.06225774829854913150
8...

result:

ok 16 numbers

Test #6:

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

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:

0.99999999999999988898
1.99999999999999977796
3.99999999999999955591
7.99999999999999911182
15.99999999999999822364
31.99999999999999644729
63.99999999999999289457
127.99999999999998578915
255.99999999999997157829
511.99999999999994315658
1023.99999999999988631316
2047.99999999999977262632
4095.9999...

result:

ok 120 numbers

Test #7:

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

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.39307159589955809054
16.45344124347663949948
14.47564008523575829201
19.04323136814423733654
16.18293241745116972652
19.04323136814423733654
19.01057653659018598091
3.30589355366057180419
11.76318762079524482544
14.66730836005563354263
16.29552563979708779129
7.61770551094769388101
16.692652903019...

result:

ok 1681 numbers

Test #8:

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

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.00000000000000000000
3.00000000000000000000
2.00000000000000000000
1.00000000000000000000
0.00000000000000024492
1.00000000000000000000
2.00000000000000000000
1.00000000000000000000
0.00000000000000048984
1.00000000000000000000
2.00000000000000000000
3.00000000000000000000
4.00000000000000000000
3...

result:

ok 108 numbers

Test #9:

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

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.21954445729288707412
3.16227766016838129914
15.03329637837290810864
6.70820393249937119151
6.00000000000000088818
19.10497317454279908588
12.00000000000000177636
0.99999999999999977796
5.65685424949237969372
4.12310562561765969747
1.41421356237309581161
5.09901951359278449161
12.369316876852980868...

result:

ok 1681 numbers

Test #10:

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

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.41421356237309581161
18.43908891458577414824
4.47213595499957872192
12.04159457879229400135
14.31782106327635339937
10.44030650891055067575
19.02629759044044988059
15.03329637837290988500
3.60555127546398868077
8.54400374531753215024
18.02775637731994606838
17.46424919657298246989
20.0000000000000...

result:

ok 1681 numbers

Test #11:

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

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.34166796558825751617
7.61577310586390954228
19.23539988168189296402
17.26268044470510076849
14.14213562373095101066
18.02776437299067424647
10.19804687967651979363
11.70469991071962390095
5.99999999999999911182
16.03121954188139852704
14.03567683526718568032
3.00000000000000044409
7.2801252890471...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781186547550533

result:

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

Test #13:

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

input:

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

output:

7.07106682092596372513

result:

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

Test #14:

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

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.00000000000000006123
0.00000000000000012246
1.00000000000000000000
0.00000000000000024492
1.00000000000000000000
2.00000000000000000000
1.00000000000000000000
0.00000000000000048984
1.00000000000000000000
2.00000000000000000000
3.00000000000000000000
4.00000000000000000000
5.00000000000000000000
6...

result:

ok 36 numbers

Test #15:

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

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.31827318950744043491
3.14737923922355067319
3.04300366455654014430
5.60113965763751231464
6.29475847844710134638
6.55343849685729029630
6.08600732911308028861
7.48016453311801310377

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 112ms
memory: 6160kb

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.99886570186870393684
14.52542301876111707770
21.07310211779425301870
31.84318911324106693428
115.92489501361566794913
49.99139105493989632123
60.50662971644160847973
69.95813003958585341024
134.90230815124220953294
90.17256143142294888548
100.22015141166821194929
110.15485288507004213443
119.8381...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 112ms
memory: 6212kb

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.00000000000000000000
15.29584130896824589740
21.47208150315872998704
30.83930851980043286176
35.00655527252372678504
50.93145810747731871970
60.50661982899774926636
70.36379544220172022051
80.00703893711576597525
90.05617132162736027112
100.00063329305191928142
110.05050827977390781598
119.838128...

result:

ok 99999 numbers

Test #18:

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

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.00000000000000000000
11.79353732894214523697
15.00685156937893616202
30.31687408905213132471
40.11390682085933434564
50.14093371745012461815
60.17558431525919360183
70.36379544220172022051
80.12553480139246175895
89.85635145977330751066
100.00063329305191928142
109.95516961431412994443
119.767282...

result:

ok 99999 numbers

Test #19:

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

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.24811447702813893557
1548.72811091166499863903
1574.07085019194778396923
1568.85515660963483242085
1558.58257813903537680744
1562.01476409869337658165
1556.58427177907310579030
1558.56463800755045667756
1566.85054815815556139569
1566.94850782386333776230
1544.53941220916726706491
1556.4551977...

result:

ok 1781 numbers

Test #20:

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

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.06834344926755875349
455444.03730527102015912533
455456.30660965142305940390
455477.37004875385900959373
455453.18351503770099952817
455440.18706222856417298317
455465.03076493635307997465
455465.71064261469291523099
455475.71220190275926142931
455459.63788507122080773115
455454.6035687641124...

result:

ok 1781 numbers

Test #21:

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

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.47448608081322163343
284359.79373264516470953822
284363.97387831337982788682
284349.90822609415045008063
284348.81350970570929348469
284360.55981077032629400492
284354.99743161693913862109
284364.12474533746717497706
284362.68000457558082416654
284362.49679081945214420557
64050.72021068462345...

result:

ok 1781 numbers

Test #22:

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

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.62139464303618296981
393120.74490368162514641881
393130.18935158872045576572
393123.05859969067387282848
393128.13429689733311533928
393119.03337907308014109731
393131.71643136371858417988
393123.27562185865826904774
393117.28858538612257689238
393128.21922607201850041747
393128.2976373296696...

result:

ok 1781 numbers

Test #23:

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

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.93541503939195536077
234686.78076298278756439686
234696.22405209683347493410
234689.23462418915005400777
234681.50983354126219637692
234688.32522228438756428659
234690.98553042093408294022
234685.31470146880019456148
234697.88306297358940355480
234685.98333338464726693928
234683.3429209643800...

result:

ok 1781 numbers

Test #24:

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

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.44641863711876794696
427613.18543997505912557244
427604.19693780248053371906
427623.36897196958307176828
427607.13360153889516368508
427612.81641323305666446686
427615.35449848003918305039
427597.85368265007855370641
427608.72995587240438908339
427602.78677933779545128345
427604.0377032625256...

result:

ok 1781 numbers

Test #25:

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

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.91651688570254918886
4368.07587066584619606147
4363.00200987500102201011
4351.15785636977670947090
4369.07182157043735060142
4360.81011560247588931816
4359.49612861851346679032
4364.15210823206507484429
4372.29116491934928490082
4363.80849163730363216018
4356.86540607719143736176
4360.211548211...

result:

ok 1781 numbers

Test #26:

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

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.60332543740514665842
730974.08228288509417325258
730965.48510232404805719852
730979.79298754595220088959
730970.73839133058208972216
731000.14045905240345746279
730970.30922725400887429714
730996.55786904785782098770
730961.61555121373385190964
730976.59082960977684706450
730959.8001171693904...

result:

ok 1781 numbers

Test #27:

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

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.20626779191661626101
1169879.34847451513633131981
372097.80616288073360919952
372088.17689014505594968796
372081.49799024569801986217
372081.01466974924551323056
372057.62184672703733667731
372089.50173864315729588270
372069.49100418167654424906
372077.25418042473029345274
372071.926200642948...

result:

ok 1781 numbers

Test #28:

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

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.07376774070489489077
10.85847445599355687307
7.64939994718610272173
8.50496140732014360708
9.38455903041469774450
7.83287542353683097218
1.44265209755929135760
15.73422639339602113751
16.86631150619566454907
12.60790007384328426099
21.79197009460837008987
6.47758784363573791865
6.1759278455934181...

result:

ok 1781 numbers

Test #29:

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

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.00000000000000000000
10.19803902718556898321
12.42802655785365217866
1330347.14979609800502657890
8.23580154719297397037
10.50979753005336014837
11.66673469194393319981
8.60232526704262667749
15.56737440130825689266
3.60555127546398912486
19.20937271229854559351
20.44636456363728171937
7.21110255...

result:

ok 1781 numbers

Test #30:

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

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.40402053276183913511
20.38893258992807488994
10.21955664412365116789
20.92534569622092632812
5.04413112193666712813
12.24807920641325154065
2.87548450340290084881
2.68850551351012567736
16.34866142039524561369
12.64724874206813787225
11.53339402876859232094
1.36333233434576994725
23.96443357152122...

result:

ok 1781 numbers

Test #31:

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

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.93989124509307231392
7.63615483712675491290
9.39324017286397783266
10.38278618100481942577
14.47032346972502381277
7.06354246918560679802
8.73037670224202244640
24.09276694941690877272
201368.83607597748050466180
5.39690588755208811023
9.10644503465140253695
17.82881558180121928103
24.47023713306...

result:

ok 1781 numbers

Test #32:

score: 0
Accepted
time: 2ms
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.71450244497835946333
25.43608921323345484211
16.87629565095395989260
26.16413213478040589166
11.36667832633835040212
31.20004726015413609730
26.95662279696948715468
25.93429053935609829296
22.98766678237099014837
28.22278807891007801345
10.74902602514249849719
5.69908752252147543516
26.9307963938...

result:

ok 1781 numbers

Test #33:

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

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.12090029354400044781
12.27722766850291158391
25.75671338183035175007
6.99411152460938101427
23.98251597080214381208
7.03921647416179130374
11.85113629277333124890
20.90902381256524122932
16.75154438828079150881
14.31298191630662408613
15.17241820806568242119
24.93579736135751545589
17.09370492725...

result:

ok 1781 numbers

Test #34:

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

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.93265086959469911676
7.21110255092797824972
5.00000000000000000000
12.18229431634250659044
18.00000000000000000000
0.27740242377880125479
12.93304077341872293516
1024855.13624225952662527561
12.41912355714126192652
3.25576411921994113285
5.66388503009096577756
9.09781783069993643664
16.0561514691...

result:

ok 1781 numbers

Test #35:

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

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.56875398168403101806
25.12981263992506697491
22.08819798794809941000
19.74962706867919592923
15.39533234087336310836
17.10471349105377925071
17.16955228129371491264
13.35059610439580524144
22.12051687334085059433
22.16603146123822298819
26.00609505095313878087
12.79694770645873624915
17.014458537...

result:

ok 1781 numbers

Test #36:

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

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.23606797749978980505
8.79600299943188090879
15.69729177253274521320
19.47576133438756684768
9.05538513813741730019
11.39467105240484201545
5.09901951359278449161
19.00000000000000000000
8.61941833972737292413
9.19252551353226721176
16.67202079529066338637
714191.23933719599153846502
13.98942591052...

result:

ok 1781 numbers

Test #37:

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

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.97777229046560498738
2.75012077389521358839
0.84677770800535268059
1.46407105292367001326
0.58578643762690496555

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 40ms
memory: 6196kb

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.46248816497675182546
15.75079676329539779545
53.67824223495885860302
82.36844406932324602622
13.98380096871968092387
37.94962440776193091097
19.41738273992307384219
26436.95480431444957503118
16.27654605203515458811
17.45511546384397760789
41.13974261838171742056
10.88638512689290038793
2.54127701...

result:

ok 100 numbers

Test #39:

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

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.97226336438325233757
1395.00626268943346985907
65837.71604013298929203302
3799.08578263525123475119
3433.75828383978705460322
194.09069222749872096756
7369.21072563029520097189
265305.15313838887959718704
8568.33430215573025634512
4911.65076924880304432008
54497.52432893191871698946
3603.75368...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 117ms
memory: 4660kb

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.63617253912252635928
5614.80460005569057102548
18063.49135981585641275160
48666.35013699867704417557
29146.20215379018554813229
1712.93252009980415095924
166623.04746190996957011521
37945.22612434009352000430
14861.68974926933333335910
52982.28356151953630615026
2858.97812040758935836493
13281....

result:

ok 100000 numbers

Test #41:

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

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.00000000000000000000
7.00000000000158717484
7.00000000000158717484
7.00000000000000000000
9.00000000000000000000
9.00000000000000000000
9.00000000000000000000
9.00000000000000000000
1.00762098240323560994
2.00000000000000000000
11.40176214459073200658
11.40175425099137918039
8.00630549996367513188...

result:

ok 99999 numbers

Test #42:

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

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.86929604823286776849
10.54708410173135391119
20.33824546278124500986
11.04723917744685834919
29307.64374632908220519312
8.69693918285445732863
12.98220524112917040327
42.20882568567321158071
18.28484683665807608577
1.32450142281070748496
89248.11332928844785783440
10.69873025810975342154
12.063924...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 134ms
memory: 6076kb

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.61814054922433570027
10.73544451753244466374
2.72967149924109531156
305762.77751817018724977970
18.13077779022443891677
24.25476820949687706275
9.75060163023107762115
7.18119923731859000071
9.18552821067295965918
51.86404205202418182807
57.78419218036127347204
304131.58640527212992310524
91.1...

result:

ok 100000 numbers

Test #44:

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

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.04023312560003722282
17.84258458082916476428
17.07511454437379683213
11.28095258305394565923
219404.30629707698244601488
27.07762553355265566779
228139.77501133776968345046
14.18968959521345318819
32.15168476963862076445
13.95880725908043196171
30.47490157274101463258
352634.11064561916282400489
2...

result:

ok 100000 numbers