QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187536#3854. RadarFlying2018#WA 1ms8396kbC++143.6kb2023-09-24 17:57:442023-09-24 17:57:44

Judging History

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

  • [2023-09-24 17:57:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8396kb
  • [2023-09-24 17:57:44]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define db double
using namespace std;

const db eps=1e-9;
const db inf=1e20;

int sgn (db x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
int comp (double x,double y){
    return sgn(x-y);
}
bool Less(double x,double y){
    return comp(x,y)==-1;
}

const int MAXN=2e5+7;

struct point{
    double x,y;
    point(){};
    point(db _x,db _y):x(_x),y(_y){};
    double operator^(const point &b)const {
        return x * b.y - y *b.x;
    }
    double operator*(const point &b){
        return x * b.x + y * b.y;
    }
    point operator+(const point &b)const {
        return point(x+b.x,y+b.y);
    }    
    point operator-(const point &b)const {
        return point(x-b.x,y-b.y);
    }
    point operator*(const double &k)const{
        return point(x*k,y*k);
    }
    point operator/(const double &k)const{
        return point(x/k,y/k);
    }
    double len2()
    {
        return x*x+y*y;
    }
    double len(){
        return hypot(x,y);
    }
    double distance(point p){
        return hypot(x-p.x,y-p.y);
    }
}a[MAXN];
struct Line {
    point p;
    point v;
    double rad;
    Line(){};

    Line(point _p,point _v):p(_p),v(_v){
        rad = atan2(v.y,v.x);
    };

    bool operator<(const Line &x){
        return Less(rad,x.rad);
    }
    
    point lineprog(point a){
        return p+(((v-p)*((v-p)*(a-p)))/(v-p).len2());
    }
}b[MAXN];

bool cmprad(Line A,Line B){
    return Less(A.rad,B.rad);
}

int R,F,N;
db rl[MAXN];
db nans;

inline void calc(point a,db d,point b){
    // printf("%lf %lf -> b\n",a.x/a.len()*d,a.y/a.len()*d);
    point a0 = point(a.x/a.len()*d,a.y/a.len()*d);
    nans=min(nans,a0.distance(b));
}


inline void check(Line a,point b){
    // printf("%lf %lf ?!\n",a.v.x,a.v.y);
    point tmp = a.lineprog(b);
    // printf("%lf %lf %lf %lf\n",b.x,b.y,tmp.x,tmp.y);
    int t= lower_bound(rl+1,rl+R+1,tmp.len()) - rl;
    // printf("%lf %d\n",b.len(),rl[t]);
    calc(a.v,rl[1],b);
    calc(a.v,rl[R],b);
    if(t!=R+1){
        if(t!=R)calc(a.v,rl[t+1],b);
        if(t!=R-1)calc(a.v,rl[t+2],b);
        calc(a.v,rl[t],b);
        if(t!=1)calc(a.v,rl[t-1],b);
        if(t!=2)calc(a.v,rl[t-2],b);
    }
}

inline void solve(){

    for(int i=1;i<=N;++i){
        if(F==1){
            nans=1e18;
            check(b[1],a[i]);
            printf("%.12lf\n",nans);
            continue;
        }      
        int t = lower_bound(b+1,b+F+1,Line(point(0,0),a[i])) - b;
        nans=1e18;
        check(b[1],a[i]);
        check(b[F],a[i]); 
        check(b[2],a[i]);  
        check(b[F-1],a[i]);     
        if(!(t==F+1 || t==1)){
            check(b[t],a[i]);
            check(b[t-1],a[i]);
            if(t!=F)check(b[t+1],a[i]);
            if(t!=2)check(b[t-2],a[i]);
        }
        printf("%.12lf\n",nans);
    }
    return ;
}

int main(){
    scanf("%d%d%d",&R,&F,&N);
    for(int i=1;i<=R;++i){
        scanf("%lf",&rl[i]);
    }
    sort(rl+1,rl+R+1);
    for(int i=1;i<=F;++i){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        b[i]=Line(point(0.0,0.0),point(a[i].x,a[i].y));
    }
    sort(b+1,b+F+1,cmprad);
    // printf("%lf %lf %lf %lf\n",atan2(3,0),atan2(-2,0),atan2(0,3),atan2(0,-3));
    // for(int i=1;i<=F;++i){
    //     printf("%lf %lf\n",b[i].v.x,b[i].v.y);
    // }
    for(int i=1;i<=N;++i){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    solve();
    return 0;
}
/*

3 1 1
1 2 3
3 3
1 -2


3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

*/

詳細信息

Test #1:

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

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.605291072917
0.977772290466
1.551845105402
1.414213562373

result:

ok 4 numbers

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 8396kb

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.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
2.236067977500
2.236067977500
2.236067977500
2.236067977500
2.236067977500
2.236067977500
2.236067977500
2.236067977500
2.000000000000
2.000000000000
2.000000000000
2.00000...

result:

wrong answer 9th numbers differ - expected: '4.9296567', found: '2.2360680', error = '0.5464049'