QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194975#3854. Radarrealcomplex0#WA 0ms3876kbC++142.7kb2023-09-30 23:58:402023-09-30 23:58:41

Judging History

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

  • [2023-09-30 23:58:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2023-09-30 23:58:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct angle{
    ld x;
    ld y;
    bool operator< (const angle &aa) const {
        return x * aa.y - y * aa.x > 0;
    }
};

vector<ld> radii;
set<angle> ang;

ld si;
ld co;

ld calc(ld x, ld y, ld rad){
    ld xi = si * rad;
    ld yi = co * rad;
    return (x - xi) * (x - xi) + (y - yi) * (y - yi);
}

int main(){
    fastIO;
    //freopen("in_a.txt", "r", stdin);
    int r, f, n;
    cin >> r >> f >> n;
    ld rr;
    for(int i = 0 ; i < r; i ++ ){
        cin >> rr;
        radii.push_back(rr);
    }
    sort(radii.begin(), radii.end());
    ld x, y;
    for(int i = 0 ; i < f; i ++ ){
        cin >> x >> y;
        ang.insert({x,y});
    }
    ld cur_ang;
    ld cur;
    ld res;
    int lf, rf;
    int cl, cr;
    for(int iq = 0 ; iq < n; iq ++ ){
        cin >> x >> y;
        auto it = ang.upper_bound({x,y});
        auto pv = it;
        res = (ld)1e18;
        for(int iter = 0; iter < 2; iter ++ ){
            cur = atan2(it->x, it->y);
            si = sin(cur);
            co = cos(cur);
            lf = 0;
            rf = r - 1;
            while(lf + 2 < rf){
                cl = (lf + lf + rf) / 3;
                cr = (lf + rf + rf) / 3;
                if(calc(x, y, radii[cl]) < calc(x, y, radii[cr])){
                    rf = cr;
                }
                else{
                    lf = cl;
                }
            }
            for(int i = lf; i <= rf; i ++ ){
                res = min(res, calc(x, y, radii[i]));
            }
            it ++ ;
            if(it == ang.end()){
                it = ang.begin();
            }
        }
        for(int iter = 0; iter < 2; iter ++ ){
            if(pv == ang.begin()){
                pv = ang.end();
            }
            pv -- ;
            cur = atan2(pv->x, pv->y);
            si = sin(cur);
            co = cos(cur);
            lf = 0;
            rf = r - 1;
            while(lf + 2 < rf){
                cl = (lf + lf + rf) / 3;
                cr = (lf + rf + rf) / 3;
                if(calc(x, y, radii[cl]) < calc(x, y, radii[cr])){
                    rf = cr;
                }
                else{
                    lf = cl;
                }
            }
            for(int i = lf; i <= rf; i ++ ){
                res = min(res, calc(x, y, radii[i]));
            }
        }
        cout << fixed << setprecision(8) << sqrt(res) << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107
0.97777229
1.55184511
1.41421356

result:

ok 4 numbers

Test #2:

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

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.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
2.00000000
2.00000000
2.00000000
4.95000256
0.07106781
0.07106781
0.07106781
0.07106781
2.00000000
2.00000000
2.0000...

result:

wrong answer 20th numbers differ - expected: '2.0000000', found: '4.9500026', error = '1.4750013'