QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346701#3854. RadarKirill22#WA 5ms3940kbC++232.2kb2024-03-08 21:23:472024-03-08 21:23:47

Judging History

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

  • [2024-03-08 21:23:47]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3940kb
  • [2024-03-08 21:23:47]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#define ld long double
#define point pair<ld, ld>
#define x first
#define y second

point operator-(point a, point b) {
    return {a.x - b.x, a.y - b.y};
}

point operator*(point a, ld d) {
    return {a.x * d, a.y * d};
}

ld sq(point a) {
    return sqrtl(a.x * a.x + a.y * a.y);
}

ld sin(point a, point b) {
    return a.x * b.y - a.y * b.x;
}

int id(point a) {
    if (a.y > 0 || (a.y == 0 && a.x >= 0)) {
        return 0;
    }
    return 1;
}

bool cmp(point a, point b) {
    if (id(a) != id(b)) return id(a) < id(b);
    if (sin(a, b) == 0) return a < b;
    return sin(a, b) > 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int R, n, q;
    cin >> R >> n >> q;
    vector<ld> r(R);
    for (auto& x : r) {
        cin >> x;
    }
    std::sort(r.begin(), r.end());
    vector<point> a(n);
    for (auto& x : a) {
        cin >> x.x >> x.y;
        x = x * (1 / (ld) sq(x));
    }
    std::sort(a.begin(), a.end(), cmp);
    while (q--) {
        point t;
        cin >> t.x >> t.y;
        ld ans = 1e18;
        int it = std::lower_bound(a.begin(), a.end(), t, cmp) - a.begin();
        for (int x = -10; x <= 10; x++) {
            int i = (it + x) % n;
            if (i < 0) i += n;
//                if (i == n - 1) {
//                    cout << a[i].x << " " << a[i].y << endl;
//                    cout << a[i].x * 4 << " " << a[i].y * 4 << endl;
//                }
//            ans = min(ans, sq(t - a[i] * r[j]));
            ld d = abs(a[i].x * t.x + a[i].y * t.y);
            int it2 = std::lower_bound(r.begin(), r.end(), d) - r.begin();
//        cout << d << "  " << it << endl;
//        for (int i = 0; i < R; i++) upd(i);
            if (it2 < r.size()) {
                ans = min(ans, sq(t - a[i] * r[it2]));
            }
            if (it2 + 1 < r.size()) {
                ans = min(ans, sq(t - a[i] * r[it2 + 1]));
            }
            if (it2) {
                ans = min(ans, sq(t - a[i] * r[it2 - 1]));
            }
        }
        cout << fixed << setprecision(15) << ans << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.605291072916640
0.977772290465605
1.551845105401790
1.414213562373095

result:

ok 4 numbers

Test #2:

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

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.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
15.874985099257575
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
4.929656701045723
2.00...

result:

ok 32 numbers

Test #3:

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

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.055385138137417
4.123105625617661
3.605551275463989
11.045361017187261
15.297058540778354
1.414213562373095
8.246211251235321
7.000000000000000
8.944271909999159
3.000000000000000
12.165525060596439
5.000000000000000
5.099019513592785
11.180339887498948
1.414213562373095
2.000000000000000
2.000000...

result:

ok 1681 numbers

Test #4:

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

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.895656100977256
12.291422905366941
6.555964003580544
4.270304206047021
4.392536000447645
6.367825885745278
6.555964003580544
2.990316379370501
10.187520359495127
2.833626166508712
2.977064831365349
4.696779860161953
4.352239888693120
11.328455809796768
3.384030...

result:

ok 1681 numbers

Test #5:

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

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
5.000000000000000
5.000000000000000
5.000000000000000
5.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
1.000000000000000
8.062257748298550
8.062257748298550
8.062257748298550
8.062257748298550

result:

ok 16 numbers

Test #6:

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

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.000000000000000
2.000000000000000
4.000000000000000
8.000000000000000
16.000000000000000
32.000000000000000
64.000000000000000
128.000000000000000
256.000000000000000
512.000000000000000
1024.000000000000000
2048.000000000000000
4096.000000000000000
8192.000000000000000
16384.000000000000000
32768...

result:

ok 120 numbers

Test #7:

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

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.453441243476639
14.475640085235758
19.043231368144237
16.182932417451168
19.043231368144237
19.010576536590187
3.305893553660572
11.763187620795244
14.667308360055634
16.295525639797088
7.617705510947693
16.692652903019119
25.870057685088936
16.182932198759698
20.084870431584898...

result:

ok 1681 numbers

Test #8:

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

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.000000000000000
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000000000
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: 3916kb

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.219544457292887
3.162277660168379
15.033296378372908
6.708203932499369
6.000000000000000
19.104973174542800
12.000000000000000
1.000000000000000
5.656854249492380
4.123105625617661
1.414213562373095
5.099019513592785
12.369316876852982
19.235384061671345
6.000000000000000
9.486832980505138
6.32455...

result:

ok 1681 numbers

Test #10:

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

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.414213562373095
18.439088914585775
4.472135954999579
12.041594578792295
14.317821063276353
10.440306508910550
19.026297590440448
15.033296378372908
3.605551275463989
8.544003745317531
18.027756377319946
17.464249196572981
20.000000000000000
5.000000000000000
13.341664064126334
10.049875621120890
1...

result:

ok 1681 numbers

Test #11:

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

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.341667965588257
7.615773105863908
19.235399881681894
17.262680444705100
14.142135623730950
18.027764372990675
10.198046879676520
11.704699910719625
6.000000000000000
16.031219541881397
14.035676835267186
3.000000000000000
7.280125289047176
20.099751242241781
14.142139587489014
13.000000000000000
...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.071067811865475

result:

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

Test #13:

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

input:

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

output:

7.071066820925964

result:

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

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3820kb

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.000000000000000
0.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
1.000000000000000
0.000000000000000
1.000000000000000
2.000000000000000
3.000000000000000
5.000000000000000
6.000000000000000
9.000000000000000
10.000000000000000
11.000000000000000
12.0000000...

result:

wrong answer 12th numbers differ - expected: '4.0000000', found: '5.0000000', error = '0.2500000'