QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194885#3854. Radarrealcomplex0#TL 5ms3956kbC++142.5kb2023-09-30 23:19:382023-09-30 23:19:38

Judging History

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

  • [2023-09-30 23:19:38]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:3956kb
  • [2023-09-30 23:19:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

vector<ld> radii;
set<ld> ang;

ld calc(ld x, ld y, ld an, ld rad){
    ld xi = sin(an) * rad;
    ld yi = cos(an) * rad;
    return sqrt((x - xi) * (x - xi) + (y - yi) * (y - yi));
}

int main(){
    fastIO;
    //freopen("in_a.txt", "r", stdin);
    int r, f, n;
    cin >> r >> f >> n;
    ld rr;
    for(int i = 0 ; i < r; i ++ ){
        cin >> rr;
        radii.push_back(rr);
    }
    sort(radii.begin(), radii.end());
    ld x, y;
    for(int i = 0 ; i < f; i ++ ){
        cin >> x >> y;
        ang.insert(atan2(x,y));
    }
    ld cur_ang;
    ld res;
    int lf, rf;
    int cl, cr;
    for(int iq = 0 ; iq < n; iq ++ ){
        cin >> x >> y;
        cur_ang = atan2(x, y);
        auto it = ang.upper_bound(cur_ang);
        auto pv = it;
        res = (ld)1e9;
        for(int iter = 0; iter < 2; iter ++ ){
            lf = 0;
            rf = (int)radii.size() - 1;
            while(lf + 3 < rf){
                cl = (lf + lf + rf) / 3;
                cr = (lf + rf + rf) / 3;
                if(calc(x, y, *it, radii[cl]) < calc(x, y, *it, radii[cr])){
                    rf = cr;
                }
                else{
                    lf = cl;
                }
            }
            for(int i = lf; i <= rf; i ++ ){
                res = min(res, calc(x, y, *it, radii[i]));
            }
            it ++ ;
            if(it == ang.end()){
                it = ang.begin();
            }
        }
        for(int iter = 0; iter < 2; iter ++ ){
            if(pv == ang.begin()){
                pv = ang.end();
            }
            pv -- ;
            lf = 0;
            rf = (int)radii.size() - 1;
            while(lf + 3 < rf){
                cl = (lf + lf + rf) / 3;
                cr = (lf + rf + rf) / 3;
                if(calc(x, y, *pv, radii[cl]) < calc(x, y, *pv, radii[cr])){
                    rf = cr;
                }
                else{
                    lf = cl;
                }
            }
            for(int i = lf; i <= rf; i ++ ){
                res = min(res, calc(x, y, *pv, radii[i]));
            }
        }
        cout << fixed << setprecision(8) << res << "\n";
    }
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107
0.97777229
1.55184511
1.41421356

result:

ok 4 numbers

Test #2:

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

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.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
2.00000000
2.00000000
2.00000000
2.00000000
0.07106781
0.07106781
0.07106781
0.07106781
2.00000000
2.00000000
2.0000...

result:

ok 32 numbers

Test #3:

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

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.05538514
4.12310563
3.60555128
11.04536102
15.29705854
1.41421356
8.24621125
7.00000000
8.94427191
3.00000000
12.16552506
5.00000000
5.09901951
11.18033989
1.41421356
2.00000000
2.00000000
3.00000000
3.16227766
8.24621125
4.47213595
5.00000000
8.54400375
9.00000000
19.41648784
2.23606798
3.6055512...

result:

ok 1681 numbers

Test #4:

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

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.77737212
4.63159368
6.89565610
12.29142291
6.55596400
4.27030421
4.39253600
6.36782589
6.55596400
2.99031638
10.18752036
2.83362617
2.97706483
4.69677986
4.35223989
11.32845581
3.38403015
1.83645937
2.94725152
7.63513190
9.09218467
8.02697478
5.72755681
10.73846242
2.67892208
7.86903994
2.6606535...

result:

ok 1681 numbers

Test #5:

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

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.00000000
4.00000000
4.00000000
4.00000000
5.00000000
5.00000000
5.00000000
5.00000000
1.00000000
1.00000000
1.00000000
1.00000000
8.06225775
8.06225775
8.06225775
8.06225775

result:

ok 16 numbers

Test #6:

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

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.00000000
2.00000000
4.00000000
8.00000000
16.00000000
32.00000000
64.00000000
128.00000000
256.00000000
512.00000000
1024.00000000
2048.00000000
4096.00000000
8192.00000000
16384.00000000
32768.00000000
65536.00000000
131072.00000000
262144.00000000
524288.00000000
1047.00047755
2095.00023866
4190...

result:

ok 120 numbers

Test #7:

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

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.39307160
16.45344124
14.47564009
19.04323137
16.18293242
19.04323137
19.01057654
3.30589355
11.76318762
14.66730836
16.29552564
7.61770551
16.69265290
25.87005769
16.18293220
20.08487043
10.69451168
19.29511601
23.75926188
19.33616564
17.38477631
6.42433455
18.10569617
15.61689155
6.42433510
4.012...

result:

ok 1681 numbers

Test #8:

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

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.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.0...

result:

ok 108 numbers

Test #9:

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

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.21954446
3.16227766
15.03329638
6.70820393
6.00000000
19.10497317
12.00000000
1.00000000
5.65685425
4.12310563
1.41421356
5.09901951
12.36931688
19.23538406
6.00000000
9.48683298
6.32455532
4.12310563
18.02775638
4.47213595
13.34166406
2.23606798
13.15294644
7.07106781
7.28010989
3.00000000
11.045...

result:

ok 1681 numbers

Test #10:

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

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.41421356
18.43908891
4.47213595
12.04159458
14.31782106
10.44030651
19.02629759
15.03329638
3.60555128
8.54400375
18.02775638
17.46424920
20.00000000
5.00000000
13.34166406
10.04987562
18.02775638
16.00000000
1.41421356
19.10497317
17.00000000
12.16552506
10.04987562
9.84885780
13.15294644
11.7046...

result:

ok 1681 numbers

Test #11:

score: 0
Accepted
time: 5ms
memory: 3884kb

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.34166797
7.61577311
19.23539988
17.26268044
14.14213562
18.02776437
10.19804688
11.70469991
6.00000000
16.03121954
14.03567684
3.00000000
7.28012529
20.09975124
14.14213959
13.00000000
16.27880485
4.47213595
8.94427191
5.00000000
2.00000000
18.24828759
15.52417470
4.99999039
13.15293061
14.560219...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781

result:

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

Test #13:

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

input:

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

output:

7.07106682

result:

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

Test #14:

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

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.00000000
0.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
5.00000000
6.00000000
7.00000000
8.00000000
9.00000000
10.00000000
1.41421356
2.23606798
3.16227766
4.12310563
5.09901951
6.08276253
7.07106781
8.06225775
9.05538514
1....

result:

ok 36 numbers

Test #15:

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

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.31827319
3.14737924
3.04300366
5.60113966
6.29475848
6.55343850
6.08600733
7.48016453

result:

ok 8 numbers

Test #16:

score: -100
Time Limit Exceeded

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.99886579
14.52542302
21.07310212
31.84318911
115.92489501
49.99139105
60.50662972
69.95813004
134.90230815
90.17256143
100.22015141
110.15485289
119.83813806
169.25925992
139.85771381
149.90386261
159.81303402
169.92400891
209.99705092
189.71365104
199.62297502
209.78857266
219.72774753
229.76351...

result: