QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504169#3854. RadarasdfsdfAC ✓286ms23536kbC++203.9kb2024-08-04 09:33:392024-08-04 09:33:39

Judging History

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

  • [2024-08-04 09:33:39]
  • 评测
  • 测评结果:AC
  • 用时:286ms
  • 内存:23536kb
  • [2024-08-04 09:33:39]
  • 提交

answer

//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#else
#define DEBUG(...) 1234
#endif
ll disv[MAX];
pll f[MAX];
pll q[MAX];
pll rq[MAX];
ll ccw(pll p1, pll p2, pll p3) {
	return (p1.first * p2.second + p2.first * p3.second + p3.first * p1.second) - (p2.first * p1.second + p3.first * p2.second + p1.first * p3.second);
}
typedef long double ld;
ld ans[MAX];
inline ll sq(ll x) { return x * x; }
inline ld sq(ld x) { return x * x; }
ld getd(ld x1, ld y1, ld x2, ld y2) {
	return sqrt(sq(x1 - x2) + sq(y1 - y2));
}
ld getd(int fn, int qn, ll d) {
	DEBUG('f' << fn << 'q' << qn << 'd' << d << ln);
	pll fp = f[fn];
	ld fd = sqrt(sq(fp.first) + sq(fp.second));
	ld fx, fy;
	fx = (ld)fp.first / fd * d;
	fy = (ld)fp.second / fd * d;
	DEBUG("fxy" << fx << bb << fy << ln);
	ld res = getd(fx, fy, q[qn].first, q[qn].second);
	DEBUG(res << ln);
	return res;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cout << fixed;
	cout.precision(20);
	int R, F, N;
	cin >> R >> F >> N;
	int i;
	for (i = 1; i <= R; i++) cin >> disv[i];
	sort(disv + 1, disv + R + 1);
	vector<int> v;
	auto ref = [&](pll& p) {
		ll g = gcd(abs(p.first), abs(p.second));
		if (!g) return;
		p.first /= g;
		p.second /= g;
	};
	for (i = 1; i <= F; i++) {
		cin >> f[i].first >> f[i].second;
		ref(f[i]);
		v.push_back(i);
	}
	for (i = 1; i <= N; i++) {
		cin >> q[i].first >> q[i].second;
		if (!q[i].first && !q[i].second) {
			ans[i] = disv[1];
			continue;
		}
		rq[i] = q[i];
		ref(q[i]);
		v.push_back(-i);
		ans[i] = 1e18;
	}
	auto getflag = [&](pll& p) {
		if (p.first > 0 && p.second >= 0) return 0;
		if (p.first <= 0 && p.second > 0) return 1;
		if (p.first < 0 && p.second <= 0) return 2;
		if (p.first >= 0 && p.second < 0) return 3;
	};
	sort(v.begin(), v.end(), [&](int i, int j) {
		pll p1, p2;
		if (i > 0) p1 = f[i];
		else p1 = q[-i];
		if (j > 0) p2 = f[j];
		else p2 = q[-j];
		if (p1 == p2) return false;
		int f1, f2;
		f1 = getflag(p1);
		f2 = getflag(p2);
		if (f1 != f2) return f1 < f2;
		ll x = ccw(pll(0, 0), p1, p2);
		if (!x) {
			DEBUG("fuck\n");
			DEBUG(p1.first << bb << p1.second << ln);
			DEBUG(p2.first << bb << p2.second << ln);
		}
		assert(x);
		return ccw(pll(0, 0), p1, p2) >= 0;
		});
	for (i = 1; i <= N; i++) swap(rq[i], q[i]);
	int s = 0;
	for (i = 0; i < v.size(); i++) {
		if (v[i] > 0) {
			s = i;
			break;
		}
	}
	vector<int> nv;
	for (i = s; i < v.size(); i++) nv.push_back(v[i]);
	for (i = 0; i < s; i++) nv.push_back(v[i]);
	v = nv;
	v.push_back(v[0]);
	int pv = 0;

	DEBUG("asdf");
	for (i = 0; i < v.size(); i++) DEBUG(v[i] << bb);
	DEBUG(ln);

	for (i = 0; i < v.size(); i++) {
		if (v[i] > 0) {
			pv = v[i];
			continue;
		}
		int qn = -v[i];
		int l, r;
		l = 1;
		r = R;
		while (r - l > 5) {
			int m = l + r >> 1;
			ld r1, r2;
			r1 = getd(pv, qn, disv[m]);
			r2 = getd(pv, qn, disv[m + 1]);
			if (r1 < r2) r = m + 1;
			else l = m;
		}
		for (int j = l; j <= r; j++) ans[qn] = min(ans[qn], getd(pv, qn, disv[j]));
	}
	for (i = v.size() - 1; i >= 0; i--) {
		if (v[i] > 0) {
			pv = v[i];
			continue;
		}
		int qn = -v[i];
		int l, r;
		l = 1;
		r = R;
		while (r - l > 5) {
			int m = l + r >> 1;
			ld r1, r2;
			r1 = getd(pv, qn, disv[m]);
			r2 = getd(pv, qn, disv[m + 1]);
			if (r1 < r2) r = m + 1;
			else l = m;
		}
		for (int j = l; j <= r; j++) ans[qn] = min(ans[qn], getd(pv, qn, disv[j]));
	}
	for (i = 1; i <= N; i++) cout << ans[i] << ln;
}

详细

Test #1:

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

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.60529107291664006895
0.97777229046560480978
1.55184510540178987844
1.41421356237309504876

result:

ok 4 numbers

Test #2:

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

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.87498509925757547191
15.87498509925757547191
15.87498509925757547191
15.87498509925757547191
15.87498509925757547191
15.87498509925757547191
15.87498509925757547191
15.87498509925757547191
4.92965670104572284979
4.92965670104572284979
4.92965670104572284979
4.92965670104572284979
4.92965670104572...

result:

ok 32 numbers

Test #3:

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

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.05538513813741662625
4.12310562561766054965
3.60555127546398929313
11.04536101718726077460
15.29705854077835449050
1.41421356237309504876
8.24621125123532109930
7.00000000000000000000
8.94427190999915878566
3.00000000000000000000
12.16552506059643937782
5.00000000000000000000
5.0990195135927848298...

result:

ok 1681 numbers

Test #4:

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

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.77737211930355110470
4.63159368259021403565
6.89565610097725717074
12.29142290536694126502
6.55596400358054417004
4.27030420604702070286
4.39253600044764539118
6.36782588574527809097
6.55596400358054417004
2.99031637937050122139
10.18752035949512855378
2.83362616650871192289
2.9770648313653492018...

result:

ok 1681 numbers

Test #5:

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

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
5.00000000000000000000
5.00000000000000000000
1.00000000000000000000
1.00000000000000000000
1.00000000000000000000
1.00000000000000000000
8.06225774829854965279
8...

result:

ok 16 numbers

Test #6:

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

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.00000000000000000000
2.00000000000000000000
4.00000000000000000000
8.00000000000000000000
16.00000000000000000000
32.00000000000000000000
64.00000000000000000000
128.00000000000000000000
256.00000000000000000000
512.00000000000000000000
1024.00000000000000000000
2048.00000000000000000000
4096.0000...

result:

ok 120 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 12048kb

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.39307159589955811656
16.45344124347663937111
14.47564008523575757124
19.04323136814423693582
16.18293241745116820170
19.04323136814423693582
19.01057653659018677889
3.30589355366057197896
11.76318762079524431717
14.66730836005563434234
16.29552563979708789538
7.61770551094769352279
16.692652903019...

result:

ok 1681 numbers

Test #8:

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

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

result:

ok 108 numbers

Test #9:

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

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.21954445729288731004
3.16227766016837933197
15.03329637837290827084
6.70820393249936908903
6.00000000000000000000
19.10497317454280017876
12.00000000000000000000
1.00000000000000000000
5.65685424949238019506
4.12310562561766054965
1.41421356237309504876
5.09901951359278482988
12.369316876852981649...

result:

ok 1681 numbers

Test #10:

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

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.41421356237309504876
18.43908891458577462008
4.47213595499957939283
12.04159457879229548020
14.31782106327635315478
10.44030650891055017962
19.02629759044044806433
15.03329637837290827084
3.60555127546398929313
8.54400374531753116752
18.02775637731994646563
17.46424919657298064669
20.0000000000000...

result:

ok 1681 numbers

Test #11:

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

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.34166796558825715709
7.61577310586390828547
19.23539988168189370128
17.26268044470510010062
14.14213562373095048764
18.02776437299067471831
10.19804687967651965052
11.70469991071962510918
6.00000000000000000000
16.03121954188139736477
14.03567683526718593793
3.00000000000000000000
7.2801252890471...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781186547524382

result:

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

Test #13:

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

input:

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

output:

7.07106682092596364967

result:

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

Test #14:

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

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.00000000000000000000
0.00000000000000000000
1.00000000000000000000
0.00000000000000000000
1.00000000000000000000
2.00000000000000000000
1.00000000000000000000
0.00000000000000000000
1.00000000000000000000
2.00000000000000000000
3.00000000000000000000
4.00000000000000000000
5.00000000000000000000
6...

result:

ok 36 numbers

Test #15:

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

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.31827318950744077188
3.14737923922355080004
3.04300366455654009486
5.60113965763751296429
6.29475847844710160008
6.55343849685729004477
6.08600732911308018973
7.48016453311801276464

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 265ms
memory: 21092kb

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.99886570186870361678
14.52542301876111672469
21.07310211779425101683
31.84318911324106729684
115.92489501361567239002
49.99139105493989371568
60.50662971644160500334
69.95813003958584609665
134.90230815124221208645
90.17256143142294976672
100.22015141166820755003
110.15485288507004679737
119.8381...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 248ms
memory: 20264kb

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.29584130896824535704
21.47208150315872945101
30.83930851980043384188
35.00655527252373017122
50.93145810747731713763
60.50661982899775080333
70.36379544220172457814
80.00703893711576138864
90.05617132162736709206
100.00063329305191867774
110.05050827977390910661
119.838128...

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 244ms
memory: 21380kb

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.79353732894214517278
15.00685156937894500565
30.31687408905213292933
40.11390682085933372461
50.14093371745012565205
60.17558431525919778599
70.36379544220172457814
80.12553480139246507574
89.85635145977330639350
100.00063329305191867774
109.95516961431412483741
119.767282...

result:

ok 99999 numbers

Test #19:

score: 0
Accepted
time: 3ms
memory: 12112kb

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.24811447697999255979
1548.72811091166497432514
1574.07085019194781805307
1568.85515660963480355505
1558.58257813903532928990
1562.01476409869341843706
1556.58427177907303939897
1558.56463800755049986524
1566.85054815815565210091
1566.94850782386323950757
1544.53941220916726606571
1556.4551977...

result:

ok 1781 numbers

Test #20:

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

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.06834344926576818580
455444.03730527100512404104
455456.30660965139892937259
455477.37004875385630953133
455453.18351503766353971514
455440.18706222853120380023
455465.03076493634429766644
455465.71064261470328915493
455475.71220190273734829134
455459.63788507117754988940
455454.6035687640836...

result:

ok 1781 numbers

Test #21:

score: 0
Accepted
time: 3ms
memory: 12128kb

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.47448608077786502690
284359.79373264515319874590
284363.97387831339040076273
284349.90822609414985322474
284348.81350970568618663492
284360.55981077030622827806
284354.99743161695988646898
284364.12474533742647508916
284362.68000457555726256942
284362.49679081946970882200
64050.72021068456195...

result:

ok 1781 numbers

Test #22:

score: 0
Accepted
time: 3ms
memory: 12052kb

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.62139464306119407411
393120.74490368164779852123
393130.18935158874089097480
393123.05859969069243220474
393128.13429689736753402940
393119.03337907306584497746
393131.71643136372634330655
393123.27562185865011201713
393117.28858538613474138401
393128.21922607203279653731
393128.2976373296714...

result:

ok 1781 numbers

Test #23:

score: 0
Accepted
time: 3ms
memory: 12040kb

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.93541503937656500511
234686.78076298275760791512
234696.22405209681400606314
234689.23462418917061711454
234681.50983354125376934007
234688.32522228440569733721
234690.98553042094286524843
234685.31470146877262550333
234697.88306297361404517687
234685.98333338464971120629
234683.3429209643812...

result:

ok 1781 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 12128kb

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.44641863712433860201
427613.18543997502632691976
427604.19693780245140146690
427623.36897196957488631597
427607.13360153891855475194
427612.81641323305055379933
427615.35449848002539852132
427597.85368265013067912150
427608.72995587241283033109
427602.78677933784317133359
427604.0377032625277...

result:

ok 1781 numbers

Test #25:

score: 0
Accepted
time: 3ms
memory: 12060kb

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.91651688570276146351
4368.07587066584592294660
4363.00200987500084037762
4351.15785636977638262124
4369.07182157043727199763
4360.81011560247622327324
4359.49612861851377321187
4364.15210823206482348979
4372.29116491934911392647
4363.80849163730335149580
4356.86540607719129036823
4360.211548211...

result:

ok 1781 numbers

Test #26:

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

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.60332543750286049544
730974.08228288519444504345
730965.48510232410620801602
730979.79298754600478105203
730970.73839133064296902376
731000.14045905250384294050
730970.30922725412671070444
730996.55786904797747638440
730961.61555121382610877845
730976.59082960978179244194
730959.8001171694292...

result:

ok 1781 numbers

Test #27:

score: 0
Accepted
time: 3ms
memory: 12048kb

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.20626779191240984801
1169879.34847451520477079612
372097.80616288072900488260
372088.17689014503463340588
372081.49799024567076344283
372081.01466974922502117806
372057.62184672705470234177
372089.50173864315144101056
372069.49100418166412396204
372077.25418042474009894249
372071.926200642951...

result:

ok 1781 numbers

Test #28:

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

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.07376774070489638610
10.85847445599355801018
7.64939994718610375302
8.50496140732014418127
9.38455903041469740537
7.83287542353683273596
1.44265209755929172677
15.73422639339602212977
16.86631150619566474683
12.60790007384328455329
21.79197009460837184541
6.47758784363573876779
6.1759278455934181...

result:

ok 1781 numbers

Test #29:

score: 0
Accepted
time: 3ms
memory: 12124kb

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.19803902718556965976
12.42802655785365259934
1330347.14979609811359750893
8.23580154719297430430
10.50979753005336009980
11.66673469194393262128
8.60232526704262677204
15.56737440130825721185
3.60555127546398929313
19.20937271229854606015
20.44636456363728166039
7.21110255...

result:

ok 1781 numbers

Test #30:

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

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.40402053276183845770
20.38893258992807533403
10.21955664412365301624
20.92534569622092759968
5.04413112193666622780
12.24807920641325151897
2.87548450340290192174
2.68850551351012679408
16.34866142039524608207
12.64724874206813901283
11.53339402876859548161
1.36333233434576981920
23.96443357152122...

result:

ok 1781 numbers

Test #31:

score: 0
Accepted
time: 3ms
memory: 12060kb

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.93989124509307361323
7.63615483712675501395
9.39324017286397816486
10.38278618100482026971
14.47032346972502366012
7.06354246918560665057
8.73037670224202306916
24.09276694941690979100
201368.83607597748509476787
5.39690588755208849924
9.10644503465140275986
17.82881558180121801295
24.47023713306...

result:

ok 1781 numbers

Test #32:

score: 0
Accepted
time: 3ms
memory: 12064kb

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.71450244497835974002
25.43608921323345344392
16.87629565095395748307
26.16413213478040492889
11.36667832633835064672
31.20004726015413512238
26.95662279696948603579
25.93429053935609922797
22.98766678237098956550
28.22278807891007722068
10.74902602514249804356
5.69908752252147430759
26.9307963938...

result:

ok 1781 numbers

Test #33:

score: 0
Accepted
time: 3ms
memory: 14168kb

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.12090029354399915718
12.27722766850291168713
25.75671338183035071270
6.99411152460938092840
23.98251597080214468465
7.03921647416179159951
11.85113629277333206248
20.90902381256524177749
16.75154438828079278730
14.31298191630662425006
15.17241820806568254089
24.93579736135751477068
17.09370492725...

result:

ok 1781 numbers

Test #34:

score: 0
Accepted
time: 3ms
memory: 12020kb

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.93265086959469970049
7.21110255092797858625
5.00000000000000000000
12.18229431634250621748
18.00000000000000000000
0.27740242377880130291
12.93304077341872258301
1024855.13624225955595647974
12.41912355714126199677
3.25576411921994127749
5.66388503009096528707
9.09781783069993479646
16.0561514691...

result:

ok 1781 numbers

Test #35:

score: 0
Accepted
time: 3ms
memory: 12020kb

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.56875398168403037448
25.12981263992506845983
22.08819798794810001022
19.74962706867919765182
15.39533234087336350561
17.10471349105377936693
17.16955228129371665083
13.35059610439580474357
22.12051687334085161088
22.16603146123822305411
26.00609505095313922149
12.79694770645873696992
17.014458537...

result:

ok 1781 numbers

Test #36:

score: 0
Accepted
time: 3ms
memory: 12020kb

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.23606797749978969641
8.79600299943188066159
15.69729177253274591056
19.47576133438756614338
9.05538513813741662625
11.39467105240484297128
5.09901951359278482988
19.00000000000000000000
8.61941833972737401787
9.19252551353226722477
16.67202079529066368301
714191.23933719601456004966
13.98942591052...

result:

ok 1781 numbers

Test #37:

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

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.97777229046560480978
2.75012077389521401730
0.84677770800535222582
1.46407105292367016103
0.58578643762690481452

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 58ms
memory: 14576kb

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.46248816502953175520
15.75079676329614279760
53.67824223505362457934
82.36844406927891217018
13.98380096873129845286
37.94962440779210639460
19.41738273988135545824
26436.95480431452211078636
16.27654605200351110340
17.45511546385219692201
41.13974261822779092054
10.88638512688001804864
2.54127701...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 213ms
memory: 20788kb

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.97226336441043770265
1395.00626268942960650499
65837.71604013298242819019
3799.08578263524060969480
3433.75828383985370484410
194.09069222749635455494
7369.21072563025173529638
265305.15313838889900921458
8568.33430215567843557523
4911.65076924884303277707
54497.52432893190234963754
3603.75368...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 218ms
memory: 16860kb

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.63617253912647919734
5614.80460005570312542744
18063.49135981585602195310
48666.35013699864262193273
29146.20215379020021906342
1712.93252009981759309554
166623.04746190991529886105
37945.22612434010702742171
14861.68974926942664982477
52982.28356151955988551094
2858.97812040757852036776
13281....

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 223ms
memory: 23536kb

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.00000000000158760548
7.00000000000158760548
7.00000000000000000000
9.00000000000000000000
9.00000000000000000000
9.00000000000000000000
9.00000000000000000000
1.00762098240323635468
2.00000000000000000000
11.40176214459073182964
11.40175425099137979101
8.00630549996367548056...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 279ms
memory: 23348kb

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.86929604825499639902
10.54708410168283309015
20.33824546278229297540
11.04723917745526382515
29307.64374632907387585590
8.69693918288908545018
12.98220524115137157039
42.20882568568205708490
18.28484683666392729071
1.32450142286666437013
89248.11332928845693146513
10.69873025809834680890
12.063924...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 277ms
memory: 21936kb

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.61814054917917360399
10.73544451753423979636
2.72967149934394059311
305762.77751817025060177002
18.13077779020582941047
24.25476820949982764523
9.75060163023606509859
7.18119923730584691331
9.18552821060543115469
51.86404205200081231689
57.78419218024266280562
304131.58640527213782434046
91.1...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 286ms
memory: 21916kb

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.04023312559556955722
17.84258458095912822962
17.07511454442102896700
11.28095258305308747938
219404.30629707692294516619
27.07762553352081880305
228139.77501133772467767358
14.18968959519888346863
32.15168476975007767413
13.95880725908684655539
30.47490157272388833047
352634.11064561914437831547
2...

result:

ok 100000 numbers