QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509494#3854. RadarwisniewskijWA 3ms3944kbC++202.9kb2024-08-08 15:21:432024-08-08 15:21:43

Judging History

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

  • [2024-08-08 15:21:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3944kb
  • [2024-08-08 15:21: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 : loc_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: 3868kb

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

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

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:

wrong answer 374th numbers differ - expected: '11.7890061', found: '12.2458698', error = '0.0387534'