QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187341#3854. RadarFlying2018#WA 2ms8420kbC++142.8kb2023-09-24 16:30:552023-09-24 16:30:55

Judging History

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

  • [2023-09-24 16:30:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8420kb
  • [2023-09-24 16:30:55]
  • 提交

answer

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

const db eps=1e-8;
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;
    }
    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);
    }
}b[MAXN];

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

int R,F,N;
int 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);
    int t= lower_bound(rl+1,rl+R+1,b.len()) - rl;
    // printf("%lf %d\n",b.len(),rl[t]);
    if(t==R+1){
        calc(a.v,rl[R],b);
        calc(a.v,rl[1],b);
    }else {
        calc(a.v,rl[t],b);
        if(t!=1){
            calc(a.v,rl[t-1],b);
            calc(a.v,rl[1],b);
        }
    }
}

inline void solve(){
    for(int i=1;i<=N;++i){
        int t = lower_bound(b+1,b+F+1,Line(point(0,0),a[i])) - b;
        nans=1e18;
        // printf("now %d %d\n",i,t);
        if(t==F+1 || t==1){
            check(b[1],a[i]);
            check(b[F],a[i]);
        }else {
            check(b[t],a[i]);
            check(b[t-1],a[i]);
        }
        printf("%.12lf\n",nans);
    }
    return ;
}

int main(){
    scanf("%d%d%d",&R,&F,&N);
    for(int i=1;i<=R;++i){
        scanf("%d",&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 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: 1ms
memory: 6284kb

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: 0
Accepted
time: 0ms
memory: 8420kb

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
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
2.000000000000
2.000000000000
2.000000000000
2.00000...

result:

ok 32 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 6284kb

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.055385138137
4.123105625618
3.605551275464
11.045361017187
15.297058540778
1.414213562373
8.246211251235
7.000000000000
8.944271909999
3.000000000000
12.165525060596
5.000000000000
5.099019513593
11.180339887499
1.414213562373
2.000000000000
2.000000000000
3.000000000000
3.162277660168
8.246211251...

result:

ok 1681 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 6296kb

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.777372119304
4.631593682590
6.895656100977
12.291422905367
6.555964003581
4.270304206047
4.392536000448
6.367825885745
6.555964003581
2.990316379371
10.187520359495
2.833626166509
2.977064831365
4.696779860162
4.352239888693
11.328455809797
3.384030147710
1.836459365744
2.947251516416
7.635131895...

result:

ok 1681 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 8396kb

input:

1 4 16
7
0 1
1 0
0 -1
-1 0
3 0
0 3
-3 0
0 -3
3 3
3 -3
-3 3
-3 -3
8 0
0 8
-8 0
0 -8
8 8
8 -8
-8 8
-8 -8

output:

4.000000000000
4.000000000000
4.000000000000
4.000000000000
5.000000000000
5.000000000000
5.000000000000
5.000000000000
1.000000000000
1.000000000000
1.000000000000
1.000000000000
8.062257748299
8.062257748299
8.062257748299
8.062257748299

result:

ok 16 numbers

Test #6:

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

input:

30 4 120
128
1
2
256
4
512
1024
2048
8
4096
32768
131072
262144
524288
8192
268167
16
536334
16384
1047
32
2095
8380
64
134083
65536
4190
67041
33520
16760
536334 0
-536335 0
0 536334
0 -536335
-1 1
-2 2
-4 4
-8 8
-16 16
-32 32
-64 64
-128 128
-256 256
-512 512
-1024 1024
-2048 2048
-4096 4096
-8192...

output:

1.000000000000
2.000000000000
4.000000000000
8.000000000000
16.000000000000
32.000000000000
64.000000000000
128.000000000000
256.000000000000
512.000000000000
1024.258268211685
2048.539235650614
4097.078471301227
8194.156942602454
16388.313885204909
32776.627770409817
65553.278491620847
131106.57994...

result:

wrong answer 11th numbers differ - expected: '1024.0000000', found: '1024.2582682', error = '0.0002522'