QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509529#3854. RadarwisniewskijWA 0ms3916kbC++202.7kb2024-08-08 15:41:512024-08-08 15:41:51

Judging History

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

  • [2024-08-08 15:41:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3916kb
  • [2024-08-08 15:41:51]
  • 提交

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};
}

long double dot_prod(point a, point b){
    return a.st * b.st + a.nd * b.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);
            }
        }
        vector<long double> loc_radii;
        for(auto l_angle : loc_angles){
            auto upper_radius = upper_bound(all(radii), dot_prod({(*l_angle).st, (*l_angle).nd}, pt));
            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));
                }
            }
        }
 
        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: 0
Wrong Answer
time: 0ms
memory: 3916kb

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:

5.5930600292088784318
0.9777722904656049825
1.5518451054017895745
1.4142135623730950488

result:

wrong answer 1st numbers differ - expected: '0.6052911', found: '5.5930600', error = '4.9877690'