QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#195156#3854. Radarrealcomplex0#TL 0ms0kbC++142.3kb2023-10-01 01:28:382023-10-01 01:28:38

Judging History

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

  • [2023-10-01 01:28:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-01 01:28:38]
  • 提交

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

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


int main(){
    fastIO;
    freopen("input.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(atan2(x,y));
    }
    ld cur_ang;
    ld res;
    int lf, rf;
    int cl, cr;
    ld dist;
    int yy;
    ld f1, f2;
    for(int iq = 0 ; iq < n; iq ++ ){
        cin >> x >> y;
        cur_ang = atan2(x, y);
        ld big_cos = 0;
        auto it = ang.upper_bound(cur_ang);
        auto pv = it;
        res = (ld)1e18;
        dist = sqrt(x * x + y * y);
        yy = upper_bound(radii.begin(), radii.end(), dist) - radii.begin();
        for(int iter = 0; iter < 10; iter ++ ){
            big_cos = max(big_cos, cos(cur_ang-*it));
            it ++ ;
            if(it == ang.end()){
                it = ang.begin();
            }
        }
        for(int iter = 0; iter < 10; iter ++ ){
            if(pv == ang.begin()){
                pv = ang.end();
            }
            pv -- ;
            big_cos=max(big_cos, cos(cur_ang-*pv));
        }
        int lf = 0;
        int rf = r - 1;
        while(lf + 5 < rf){
            int cl = (lf + lf + rf) / 3;
            int cr = (lf + rf + rf) / 3;
            f1 = radii[cl] * radii[cl] - 2.0 * radii[cl] * dist * big_cos + dist * dist;
            f2 = radii[cr] * radii[cr] - 2.0 * radii[cr] * dist * big_cos + dist * dist;
            if(f1 < f2){
                rf = cr;
            }
            else{
                lf = cl;
            }
        }
        for(int i = lf; i <= rf; i ++ ){
            f1 = radii[i] * radii[i] - 2.0 * radii[i] * dist * big_cos + dist * dist;
            if(f1 < res){
                res = f1;
            }
        }
        cout << fixed << setprecision(8) << sqrt(res) << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

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:


result: