QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#195005#3854. Radarrealcomplex0#WA 5ms3824kbC++141.9kb2023-10-01 00:04:582023-10-01 00:04:59

Judging History

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

  • [2023-10-01 00:04:59]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3824kb
  • [2023-10-01 00:04:58]
  • 提交

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;
    ld dist;
    int yy;
    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;
        dist = sqrt(x * x + y * y);
        yy = upper_bound(radii.begin(), radii.end(), dist) - radii.begin();
        for(int iter = 0; iter < 5; iter ++ ){
            for(int i = max(yy-3,0); i <= min(r-1,yy+2); i ++ ){
                res = min(res, calc(x, y, *it, radii[i]));
            }
            it ++ ;
            if(it == ang.end()){
                it = ang.begin();
            }
        }
        for(int iter = 0; iter < 5; iter ++ ){
            if(pv == ang.begin()){
                pv = ang.end();
            }
            pv -- ;
            for(int i = max(yy-3,0); i <= min(r-1,yy+2); 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: 1ms
memory: 3800kb

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

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: 0ms
memory: 3716kb

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

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: 1ms
memory: 3764kb

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: 0ms
memory: 3636kb

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: 4ms
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.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: 3768kb

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: 3ms
memory: 3824kb

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: 3ms
memory: 3712kb

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

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

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: 1ms
memory: 3696kb

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

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
10.00000000
11.00000000
1.41421356
2.23606798
3.16227766
4.12310563
5.09901951
6.08276253
7.07106781
8.24621125
9.21954446
1...

result:

wrong answer 17th numbers differ - expected: '9.0000000', found: '10.0000000', error = '0.1111111'