QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187406#3854. Radarballance#WA 125ms5764kbC++171.8kb2023-09-24 17:00:002023-09-24 17:00:00

Judging History

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

  • [2023-09-24 17:00:00]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:5764kb
  • [2023-09-24 17:00:00]
  • 提交

answer

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld PI = 3.14159265358;
ld angle(ld x, ld y)
{
	if (x == 0)
	{
		if (y > 0)
			return PI / 2;
		return -PI / 2;
	}
	if (x > 0)
		return atan(ld(y) / x);
	else
		if (y < 0)return -PI + atan(ld(y) / x);
		else
			return PI + atan(ld(y) / x);
}
ld len(ld x, ld y)
{
	return sqrt(x * x + y * y);
}
const int N = 100010;

int r[N];
ld a[N];
ld len2(ld alpha, ld r, ld x, ld y)
{
	ld dx = r * cos(alpha), dy = r * sin(alpha);
	return len(dx - x, dy - y);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int rr, ff, tt;
	cin >> rr >> ff >> tt;
	for (int i = 1; i <= rr; i++)
		cin >> r[i];
	sort(r + 1, r + rr + 1);
	r[0] = -1e8;
	r[rr + 1] = 1e8;
	for (int i = 1; i <= ff; i++)
	{
		int x, y; cin >> x >> y;
		a[i] = angle(x, y);
		//cout << x << ' ' << y << ' ' << a[i] << '\n';
	}
	sort(a + 1, a + ff + 1);
	a[ff + 1] = a[1] + 2 * PI;
	a[0] = a[ff] - 2 * PI;
	while (tt--)
	{
		int x, y; cin >> x >> y;
		ld leng = len(x, y);
		/*int l = lower_bound(r, r + rr + 2, leng) - r;
		int s[3];
		s[1] = r[l - 1], s[2] = r[l];*/
		ld alpha = angle(x, y);
		int l = lower_bound(a + 1, a + ff + 2, alpha) - a;
		ld p[3];
		p[1] = a[l - 1], p[2] = a[l];
		ld ans = 1e10;
		for (int i = 1; i <= 2; i++)
		{
			ld beta = p[i];
			ld shadowlen = leng * cos(beta - alpha);
			int l = lower_bound(r, r + rr + 2, shadowlen) - r;
			int s[3];
			s[1] = r[l - 1], s[2] = r[l];
			for (int j = 1; j <= 2; j++)
				ans = min(ans, len2(beta, s[j], x, y));
		}
		cout << fixed << setprecision(15) << ans << '\n';
	}
}
/*
2 1 1
1 2
1 0
-1 2

2 1 1
1 2
0 1
1 0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.605291072920783
0.977772290465605
1.551845105360774
1.414213562373095

result:

ok 4 numbers

Test #2:

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

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.874985099288110
15.874985099257575
15.874985099227040
15.874985099257575
15.874985099227040
15.874985099288110
4.929656701045723
4.929656701045723
4.929656701055556
4.929656701045723
4.929656701035890
4.929656701045723
4.929656701035890
4.929656701055556
2.00...

result:

ok 32 numbers

Test #3:

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

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.055385138215283
4.123105625655664
3.605551275420531
11.045361017265284
15.297058540701530
1.414213562317696
8.246211251311327
6.999999999921655
8.944271910069233
2.999999999843309
12.165525060519160
5.000000000023504
5.099019513592785
11.180339887344785
1.414213562373095
2.000000000000000
2.000000...

result:

ok 1681 numbers

Test #4:

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

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.895656100896918
12.291422905213700
6.555964003580544
4.270304206124859
4.392536000447645
6.367825885823576
6.555964003648145
2.990316379370501
10.187520359484252
2.833626166479386
2.977064831439783
4.696779860279904
4.352239888845865
11.328455809796768
3.384030...

result:

ok 1681 numbers

Test #5:

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

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
4.999999999979434
4.999999999979434
4.999999999958869
4.999999999958869
1.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
8.062257748264538
8.062257748264538
8.062257748230527
8.062257748230527

result:

ok 16 numbers

Test #6:

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

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.999999999990207
1.999999999980414
3.999999999960827
7.999999999921655
15.999999999843309
31.999999999686618
63.999999999373237
127.999999998746473
255.999999997492947
511.999999994985893
1023.999999989971786
2047.999999979943572
4095.999999959887144
8191.999999919774288
16383.999999839548576
32767...

result:

ok 120 numbers

Test #7:

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

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.453441243482532
14.475640085235758
19.043231368148964
16.182932417446889
19.043231368144237
19.010576536588730
3.305893553660572
11.763187620795244
14.667308360055634
16.295525639790289
7.617705510947693
16.692652903019119
25.870057685088936
16.182932198759698
20.084870431581451...

result:

ok 1681 numbers

Test #8:

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

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.000000000019586
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000039173
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: 3692kb

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.219544457273767
3.162277660019729
15.033296378353365
6.708203932359221
6.000000000078345
19.104973174503843
12.000000000078345
0.999999999980414
5.656854249436982
4.123105625541654
1.414213562428494
5.099019513554373
12.369316876776975
19.235384061593958
5.999999999921655
9.486832980579463
6.32455...

result:

ok 1681 numbers

Test #10:

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

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.414213562428494
18.439088914624015
4.472135954964542
12.041594578714221
14.317821063314656
10.440306508985591
19.026297590518685
15.033296378451080
3.605551275420531
8.544003745390888
18.027756377359059
17.464249196611112
20.000000000078345
4.999999999952993
13.341664064202673
10.049875621101401
1...

result:

ok 1681 numbers

Test #11:

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

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.341667965550088
7.615773105935919
19.235399881527120
17.262680444666523
14.142135623808508
18.027764372912450
10.198046879599696
11.704699910645997
5.999999999921655
16.031219541920494
14.035676835189040
3.000000000019586
7.280125288896514
20.099751242261270
14.142139587450235
12.999999999921655
...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.071067811850933

result:

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

Test #13:

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

input:

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

output:

7.071066820916269

result:

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

Test #14:

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

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.000000000004897
0.000000000009793
1.000000000000000
0.000000000019586
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000039173
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: 3804kb

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.318273189544933
3.147379239204565
3.043003664594787
5.601139657563804
6.294758478409130
6.553438496895029
6.086007329189575
7.480164533193865

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 118ms
memory: 5764kb

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.998865701868259
14.525423018693443
21.073102117701886
31.843189113148612
115.924895013577747
49.991391054842361
60.506629716344534
69.958130039488118
134.902308151180620
90.172561431325273
100.220151411570515
110.154852884972286
119.838138057552403
169.259259924752511
139.857713809874450
149.9038...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 125ms
memory: 5636kb

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: -100
Wrong Answer
time: 120ms
memory: 5656kb

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.006851569378945
30.316874089052133
40.113906820859334
50.140933717450126
60.175584315259198
70.363795442201725
80.125534801392465
89.856351459773306
100.000633293051919
109.955169614314125
119.767282240876358
129.812131979221724
139.932670846875566
149.713860...

result:

wrong answer 50191st numbers differ - expected: '0.2258785', found: '0.2258863', error = '0.0000077'