QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187217 | #3854. Radar | wind_whisper# | WA | 2ms | 6296kb | C++14 | 1.2kb | 2023-09-24 15:34:46 | 2023-09-24 15:34:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+100;
int r,f,n;
double d[N];
struct node{
double x,y,ang;
bool operator < (const node &oth)const{return ang<oth.ang;}
}p[N];
int Find(double ang){
int st=1,ed=f;
while(st<ed){
int mid=(st+ed+1)>>1;
if(p[mid].ang<ang) st=mid;
else ed=mid-1;
}
return st;
}
double calcdis(int i,int j,double x,double y){
double nx=d[j]/sqrt(p[i].x*p[i].x+p[i].y*p[i].y)*p[i].x,ny=d[j]/sqrt(p[i].x*p[i].x+p[i].y*p[i].y)*p[i].y;
return sqrt((nx-x)*(nx-x)+(ny-y)*(ny-y));
}
double calc(int i,double nx,double ny){
int st=1,ed=r;
double ans=2e18;
while(ed-st+1>=4){
int w=(ed-st+1)/3,mid1=st+w,mid2=ed-w;
if(calcdis(i,mid1,nx,ny)<calcdis(i,mid2,nx,ny)) ed=mid2;
else st=mid1;
}
for(int j=st;j<=ed;j++) ans=min(ans,calcdis(i,j,nx,ny));
return ans;
}
int main()
{
scanf("%d%d%d",&r,&f,&n);
for(int i=1;i<=r;i++) scanf("%lf",&d[i]);
for(int i=1;i<=f;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].ang=atan2(p[i].y,p[i].x);
}
sort(d+1,d+1+r);
sort(p+1,p+1+f);
while(n--){
double nx,ny;
scanf("%lf%lf",&nx,&ny);
double ang=atan2(ny,nx);
int x=Find(ang);
printf("%.12lf\n",min(calc(x,nx,ny),calc(x%f+1,nx,ny)));
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6252kb
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: 4236kb
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: -100
Wrong Answer
time: 2ms
memory: 6296kb
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 8.062257748299 8.944271909999 16.031219541881 12.165525060596 5.000000000000 5.099019513593 11.180339887499 1.414213562373 2.000000000000 2.000000000000 3.000000000000 3.162277660168 8.24621125...
result:
wrong answer 8th numbers differ - expected: '7.0000000', found: '8.0622577', error = '0.1517511'