QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#880766#3854. RadarychangseokTL 12ms4352kbC++172.9kb2025-02-03 19:49:242025-02-03 19:49:24

Judging History

This is the latest submission verdict.

  • [2025-02-03 19:49:24]
  • Judged
  • Verdict: TL
  • Time: 12ms
  • Memory: 4352kb
  • [2025-02-03 19:49:24]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef long double lb;
#define all(v) v.begin(), v.end()
#define M_PI 3.14159265358979323846
#define EPS 1e-6

lb getdist(ll x, ll y, ll r, lb a){
    // cout << r * cos(a) << ' ' << r * sin(a) << ' ';
    a *= M_PI / 180;

    lb dx = x - r * cos(a);
    lb dy = y - r * sin(a);

    return dx*dx + dy*dy;
}

ll n, m, q;
ll x, y, r;

vector<ll> vr;
vector<lb> angle;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed;
    cout.precision(12);

    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; i++){
        cin >> r;
        vr.push_back(r);
    }
    for (int i = 1; i <= m; i++){
        cin >> x >> y;
        angle.push_back(atan2(y,x) * 180 / M_PI);
    }

    sort(all(vr));
    sort(all(angle));

    vector<lb> tmp;
    for (int i = 0; i < m; i++){
        tmp.push_back(angle[i] - 360);
    }
    for (int i = 0; i < m; i++){
        tmp.push_back(angle[i]);
    }
    for (int i = 0; i < m; i++){
        tmp.push_back(angle[i] + 360);
    }

    // for (int i = 0; i < n; i++){
    //     cout << vr[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 0; i < m; i++){
    //     cout << angle[i] * 180 / M_PI << endl;

    //     // if (i % m == m-1) cout << endl;
    // }
    // cout << endl;
    // for (int i = 0; i < 3*m; i++){
    //     cout << tmp[i] * 180 / M_PI << endl;

    //     if (i % m == m-1) cout << endl;
    // }
    // cout << endl;
    // cout << endl;

    while (q--){
        cin >> x >> y;

        int left = 0;
        int right = n - 1;

        while (left < right){
            int mid = (left + right + 1) / 2;

            if (x*x+y*y >= vr[mid]*vr[mid]){
                left = mid;
            }else{
                right = mid - 1;
            }
        }

        // cout << x << ' ' << y << ' ' << vr[left] << '\n';

        int lr = left;
        lb theta = atan2(y, x) * 180 / M_PI;

        int lt = 0;

        left = 0;
        right = 3*m - 1;

        while (left+1 < right){
            int mid = (left + right + 1) / 2;

            if (tmp[mid] > theta + EPS) right = mid - 1;
            else left = mid;
        }

        // cout << angle[left].deg << ' ' << theta << ' ' << angle[right].deg << endl;

        lt = left;
        
        // cout << lt << ' ' << rt << endl;

        lb dist = 9e18;

        for (int ridx = lr-5; ridx <= lr+5; ridx++){
            if (ridx < 0) continue;
            if (ridx >= n) continue;

            for (int tidx = lt-5; tidx <= lt+5; tidx++){
                if (tidx < 0) continue;

                lb d = getdist(x, y, vr[ridx], angle[(tidx)%m]);
                // cout << d << endl;

                dist = min(dist, d);
            }
        }

        cout << sqrt(dist) << '\n';
        // cout << endl;
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.605291072917
0.977772290466
1.551845105402
1.414213562373

result:

ok 4 numbers

Test #2:

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

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.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
2.000000000000
2.000000000000
2.000000000000
2.00000...

result:

ok 32 numbers

Test #3:

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

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.055385138137
4.123105625618
3.605551275464
11.045361017187
15.297058540778
1.414213562373
8.246211251235
7.000000000000
8.944271909999
3.000000000000
12.165525060596
5.000000000000
5.099019513593
11.180339887499
1.414213562373
2.000000000000
2.000000000000
3.000000000000
3.162277660168
8.246211251...

result:

ok 1681 numbers

Test #4:

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

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.777372119304
4.631593682590
6.895656100977
12.291422905367
6.555964003581
4.270304206047
4.392536000448
6.367825885745
6.555964003581
2.990316379371
10.187520359495
2.833626166509
2.977064831365
4.696779860162
4.352239888693
11.328455809797
3.384030147710
1.836459365744
2.947251516416
7.635131895...

result:

ok 1681 numbers

Test #5:

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

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.000000000000
4.000000000000
4.000000000000
4.000000000000
5.000000000000
5.000000000000
5.000000000000
5.000000000000
1.000000000000
1.000000000000
1.000000000000
1.000000000000
8.062257748299
8.062257748299
8.062257748299
8.062257748299

result:

ok 16 numbers

Test #6:

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

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.000000000000
2.000000000000
4.000000000000
8.000000000000
16.000000000000
32.000000000000
64.000000000000
128.000000000000
256.000000000000
512.000000000000
1024.000000000000
2048.000000000000
4096.000000000000
8192.000000000000
16383.999999999999
32767.999999999998
65535.999999999997
131071.99999...

result:

ok 120 numbers

Test #7:

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

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.393071595900
16.453441243477
14.475640085236
19.043231368144
16.182932417451
19.043231368144
19.010576536590
3.305893553661
11.763187620795
14.667308360056
16.295525639797
7.617705510948
16.692652903019
25.870057685089
16.182932198760
20.084870431585
10.694511684541
19.295116007469
23.759261884935...

result:

ok 1681 numbers

Test #8:

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

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.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
...

result:

ok 108 numbers

Test #9:

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

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.219544457293
3.162277660168
15.033296378373
6.708203932499
6.000000000000
19.104973174543
12.000000000000
1.000000000000
5.656854249492
4.123105625618
1.414213562373
5.099019513593
12.369316876853
19.235384061671
6.000000000000
9.486832980505
6.324555320337
4.123105625618
18.027756377320
4.4721359...

result:

ok 1681 numbers

Test #10:

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

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.414213562373
18.439088914586
4.472135955000
12.041594578792
14.317821063276
10.440306508911
19.026297590440
15.033296378373
3.605551275464
8.544003745318
18.027756377320
17.464249196573
20.000000000000
5.000000000000
13.341664064126
10.049875621121
18.027756377320
16.000000000000
1.414213562373
19...

result:

ok 1681 numbers

Test #11:

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

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.341667965588
7.615773105864
19.235399881682
17.262680444705
14.142135623731
18.027764372991
10.198046879677
11.704699910720
6.000000000000
16.031219541881
14.035676835267
3.000000000000
7.280125289047
20.099751242242
14.142139587489
13.000000000000
16.278804854418
4.472135955000
8.944271909999
5....

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.071067811865

result:

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

Test #13:

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

input:

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

output:

7.071066820926

result:

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

Test #14:

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

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.000000000000
0.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
5.000000000000
6.000000000000
7.000000000000
8.000000000000
9.000000000000
10.000000000000
1.414213562373
2.236067977500...

result:

ok 36 numbers

Test #15:

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

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.318273189507
3.147379239224
3.043003664557
5.601139657638
6.294758478447
6.553438496857
6.086007329113
7.480164533118

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.998865701869
14.525423018761
21.073102117794
31.843189113241
153.586804184439
49.991391054940
60.506629716442
71.304136747255
185.430389126834
97.063707637896
110.473497929995
123.630698796005
135.359725664140
243.157701447671
162.608797453795
176.642804156470
189.584451543515
204.318441802607
30...

result: