QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187560 | #3854. Radar | Nax_hueux | WA | 1ms | 2516kb | C++14 | 2.4kb | 2023-09-24 18:04:39 | 2023-09-24 18:04:40 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#define y0 _y0
#define y1 _y1
using namespace std;
inline int read(){
int x=0,f=0; char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
return f?-x:x;
}
const int maxn=100010;
const double eps=1e-8;
const double pi=acos(-1);
int cir[maxn];
struct Point{
double x,y;
bool operator<(const Point &p)const{
return atan2(y,x)<atan2(p.y,p.x);
}
};
typedef Point Line;
inline double dot(Point p,Point q){ return p.x*q.x+p.y*q.y; }
inline double len(Point p){ return sqrt(dot(p,p)); }
inline double cross(Point p,Point q){ return p.x*q.y-p.y*q.x; }
Line line[maxn];
int R,F,N;
Line get1_line(double x,double y){
Line res=(Line){x,y};
int l=1,r=F;
while(l<r){
int mid=l+r+1>>1;
if(res<line[mid]) r=mid-1;
else l=mid;
}
if(l==1&&res<line[l]) return line[F];
return line[l];
}
Line get2_line(double x,double y){
Line res=(Line){x,y};
int l=1,r=F;
while(l<r){
int mid=l+r+1>>1;
if(res<line[mid]) r=mid-1;
else l=mid;
}
if(l<F) return line[l+1];
if(line[F]<res) return line[1];
return line[l];
}
inline double check(Line l,Point p){
double t=atan2(p.y,p.x)-atan2(l.y,l.x);
if(t<0) t+=2*pi;
if(t>=2*pi) t-=2*pi;
if(t>pi) t=2*pi-t;
double ll=len(p);
// printf("ll = %lf\n",ll);
int pp=lower_bound(cir+1,cir+R+1,ll)-cir,qq=0;
if(pp==R+1) {
pp=R,qq=1;
} else {
if(pp==1) qq=R;
else qq=pp-1;
}
//if(pp<=R) qq=pp-1;
//if(qq==0) qq=1;
//if(pp==R+1) pp=R;
//printf("%d %d\n",pp,qq);
double d1=sqrt((ll*cos(t)-cir[pp])*(ll*cos(t)-cir[pp])+ll*ll*sin(t)*sin(t));
double d2=sqrt((ll*cos(t)-cir[qq])*(ll*cos(t)-cir[qq])+ll*ll*sin(t)*sin(t));
return min(d1,d2);
}
int main(){
R=read(),F=read(),N=read();
for(int i=1;i<=R;i++) cir[i]=read();
sort(cir+1,cir+R+1);
for(int i=1;i<=F;i++) line[i].x=read(),line[i].y=read();
sort(line+1,line+F+1);
while(N--){
int x=read(),y=read();
Point p={x,y};
int tmp=lower_bound(line+1,line+F+1,p)-line;
Line l1=line[min(tmp,F)],l2=line[max(tmp-1,1)];
// Line l1=get1_line(x,y),l2=get2_line(x,y);
printf("%.12lf\n",min(check(l1,p),min(min(check(line[F],p),check(line[1],p)),check(l2,p))));
}
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2316kb
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: 2456kb
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: 1ms
memory: 2452kb
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: 1ms
memory: 2320kb
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: 0ms
memory: 2496kb
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: 0ms
memory: 2516kb
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.539235650613 4097.078471301226 8194.156942602453 16388.313885204905 32776.627770409810 65553.278491620833 131106.57994...
result:
wrong answer 11th numbers differ - expected: '1024.0000000', found: '1024.2582682', error = '0.0002522'