QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509508#3854. RadarwisniewskijTL 2ms4012kbC++203.0kb2024-08-08 15:31:432024-08-08 15:31:44

Judging History

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

  • [2024-08-08 15:31:44]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:4012kb
  • [2024-08-08 15:31:43]
  • 提交

answer

#include <bits/stdc++.h>
 
#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
 
using namespace std;
 
typedef pair<long double, long double> point;
 
long double dist(point a, point b){
    long double y = b.nd - a.nd, x = b.st - a.st;
    return sqrt(y*y + x*x);
}
 
point pos(point angle, long double rad){
    long double dis = dist(angle, {0, 0});
    if(dis == 0) return angle;
    return {rad / dis * angle.st, rad / dis * angle.nd};
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int R, F, N; cin>>R>>F>>N;
    vector<long double> radii(R); for(auto &x: radii) cin>>x;
    vector<point> angles(F), points(N); 
    for(auto &[x, y]: angles) cin>>x>>y;
    for(auto &[x, y]: points) cin>>x>>y;
    sort(all(radii));
    sort(all(angles), [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
 
    for(auto pt : points) {
        vector<vector<point>::iterator>loc_angles;
        {
            auto right_angle = upper_bound(all(angles), pt, [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
            if(right_angle == angles.end()) right_angle = angles.begin();
            loc_angles.push_back(right_angle);
            if(points.size() > 1) {
                auto left_angle = right_angle;
                if(left_angle == angles.begin()) left_angle = angles.end();
                left_angle--;
                loc_angles.push_back(left_angle);
                if(points.size() > 2) {
                if(left_angle == angles.begin()) left_angle = angles.end();
                left_angle--;
                loc_angles.push_back(left_angle);
                }
            }
        }
        // vector<long double> loc_radii;
        // {
        //     auto upper_radius = upper_bound(all(radii), sqrt(pt.st*pt.st + pt.nd*pt.nd));
        //     if(upper_radius == radii.end()) {
        //         upper_radius--;
        //         loc_radii.push_back(*upper_radius);
        //     } else {
        //         loc_radii.push_back(*upper_radius);
        //         if(upper_radius != radii.begin()) {
        //             upper_radius--;
        //             loc_radii.push_back(*(upper_radius));
        //             if(upper_radius != radii.begin()) {
        //                 upper_radius--;
        //                 loc_radii.push_back(*(upper_radius));
        //             }
        //         }
        //     }
        // }
 
        vector<long double> zzz;
        for(auto l_angle : loc_angles) {
            for(auto l_radius : radii) {
                zzz.push_back(dist(pos(*l_angle, l_radius), pt));
            }
        }
        sort(all(zzz));
        cout<<setprecision(20)<<zzz[0]<<'\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107291663996433
0.9777722904656049825
1.5518451054017895745
1.4142135623730950488

result:

ok 4 numbers

Test #2:

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

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.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.929656701045...

result:

ok 32 numbers

Test #3:

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

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.0553851381374166262
4.1231056256176605497
3.6055512754639892931
11.045361017187260775
15.297058540778354491
1.4142135623730950488
8.2462112512353210993
7
8.9442719099991587857
3
12.165525060596439378
5
5.0990195135927848299
11.180339887498948482
1.4142135623730950488
2
2
3
3.162277660168379332
8.2...

result:

ok 1681 numbers

Test #4:

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

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.777372119303551408
4.6315936825902144745
6.8956561009772562314
12.291422905366941493
6.5559640035805438938
4.2703042060470206408
4.3925360004476450668
6.3678258857452781101
6.5559640035805438938
2.9903163793705008662
10.187520359495127463
2.8336261665087121042
2.9770648313653493725
4.696779860161...

result:

ok 1681 numbers

Test #5:

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

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
4
4
4
5
5
5
5
1
1
1
1
8.0622577482985496528
8.0622577482985496528
8.0622577482985496528
8.0622577482985496528

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
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1047.0004775548099052
2095.0002386634708926
4190.0001193317405441
8380.0000596658709089
16760.000029832935533
33520.000014916467777
67041.000007458122639
134083.00000372903351
268167.00000186450981
536334.0000009...

result:

ok 120 numbers

Test #7:

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

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.3930715958995580628
16.453441243476639316
14.475640085235757517
19.043231368144236875
16.182932417451168141
19.043231368144236875
19.010576536590186713
3.3058935536605719265
11.763187620795244258
14.667308360055634381
16.295525639797087843
7.6177055109476934556
16.692652903019119082
25.87005768508...

result:

ok 1681 numbers

Test #8:

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

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
3
2
1
0
1
2
1
0
1
2
3
4
3
2
1
0
1
2
3
4
3
2
1
0
1
2
1
0
1
2
3
4
3
2
1
0
1
2
3
4
4.1231056256176605497
4.4721359549995793928
5
5.6568542494923801951
6.4031242374328486864
7.2111025509279785863
8.0622577482985496528
8.9442719099991587857
9.8488578017961047216
10.770329614269008063
11.704699910719625...

result:

ok 108 numbers

Test #9:

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

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.21954445729288731
3.162277660168379332
15.033296378372908271
6.708203932499369089
6
19.104973174542800179
12
1
5.6568542494923801951
4.1231056256176605497
1.4142135623730950488
5.0990195135927848299
12.369316876852981649
19.235384061671344753
6
9.4868329805051379959
6.3245553203367586639
4.1231056...

result:

ok 1681 numbers

Test #10:

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

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.4142135623730950488
18.43908891458577462
4.4721359549995793928
12.04159457879229548
14.317821063276353155
10.44030650891055018
19.026297590440448064
15.033296378372908271
3.6055512754639892931
8.5440037453175311675
18.027756377319946466
17.464249196572980647
20
5
13.341664064126333713
10.049875621...

result:

ok 1681 numbers

Test #11:

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

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.34166796558825713
7.6157731058639082855
19.235399881681893625
17.262680444705100078
14.142135623730950488
18.02776437299067473
10.198046879676519698
11.704699910719625109
6
16.031219541881397365
14.035676835267185921
3
7.2801252890471757242
20.09975124224178054
14.142139587489013886
13
16.2788048...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.0710678118654752438

result:

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

Test #13:

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

input:

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

output:

7.0710668209259636453

result:

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

Test #14:

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

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
0
1
0
1
2
1
0
1
2
3
4
5
6
7
8
9
10
1.4142135623730950488
2.2360679774997896964
3.162277660168379332
4.1231056256176605497
5.0990195135927848299
6.0827625302982196889
7.0710678118654752438
8.0622577482985496528
9.0553851381374166262
1.4142135623730950488
2.2360679774997896964
3.162277660168379332
4...

result:

ok 36 numbers

Test #15:

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

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.3182731895074407177
3.147379239223550823
3.043003664556540048
5.6011396576375128377
6.294758478447101646
6.5534384968572901029
6.0860073291130800961
7.4801645331180126558

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:


result: