QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187175 | #3854. Radar | veg# | WA | 0ms | 8344kb | C++14 | 1.6kb | 2023-09-24 15:09:12 | 2023-09-24 15:09:12 |
Judging History
answer
#include<bits/stdc++.h>
#define db long double
#define ll long long
using namespace std;
const int N=2e5+5;
int p,f,n,d[N],x[N],y[N],l1[N],l2[N];
struct A{int x,y,q;}q[N];
bool cmp(A u,A v) {
return atan2(u.y,u.x)<atan2(v.y,v.x);
}
db Dist(db xx,db yy) {
return sqrt(xx*xx+yy*yy);
}
db dist(int dis,int id,int i) {
int xx=q[id].x,yy=q[id].y;
db Dis=Dist(xx,yy);
db xxx=dis/Dis*xx,yyy=dis/Dis*yy;
return Dist(xxx-x[i],yyy-y[i]);
}
db ask(int id,int i) {
int xx=x[i],yy=y[i],xxx=q[id].x,yyy=q[id].y;
db dis=(1ll*xx*xxx+1ll*yy*yyy)/Dist(xxx,yyy);
int l=1,r=p,mid,ret=0;
while(l<=r) {
mid=l+r>>1;
if(dis<d[mid]) r=mid-1;
else l=mid+1,ret=mid;
}
db ans=1e9;
if(ret) ans=dist(d[ret],id,i);
ret++;
if(ret<=p) ans=min(ans,dist(d[ret],id,i));
return ans;
}
int main() {
scanf("%d%d%d",&p,&f,&n);
for(int i=1;i<=p;++i) {
scanf("%d",&d[i]);
}
sort(d+1,d+p+1);
for(int i=1;i<=f;++i) {
scanf("%d%d",&q[i].x,&q[i].y);
}
for(int i=1;i<=n;++i) {
scanf("%d%d",&q[f+i].x,&q[f+i].y);
q[f+i].q=i;
x[i]=q[f+i].x,y[i]=q[f+i].y;
}
int m=n+f;
sort(q+1,q+m,cmp);
int lst=0,kk=0;
for(int i=1;i<=m;++i) {
if(q[i].q==0) {
kk=i;
break;
}
}
lst=kk;
for(int i=kk+1;i<=m;++i) {
if(q[i].q!=0) l1[q[i].q]=lst;
else lst=i;
}
for(int i=1;i<kk;++i) {
if(q[i].q!=0) l1[q[i].q]=lst;
else lst=i;
}
lst=kk;
for(int i=kk-1;i>=1;--i) {
if(q[i].q!=0) l2[q[i].q]=lst;
else lst=i;
}
for(int i=m;i>kk;--i) {
if(q[i].q!=0) l2[q[i].q]=lst;
else lst=i;
}
for(int i=1;i<=n;++i) {
printf("%.12Lf\n",min(ask(l1[i],i),ask(l2[i],i)));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8344kb
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 9.423321594492
result:
wrong answer 4th numbers differ - expected: '1.4142136', found: '9.4233216', error = '5.6632946'