QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187175#3854. Radarveg#WA 0ms8344kbC++141.6kb2023-09-24 15:09:122023-09-24 15:09:12

Judging History

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

  • [2023-09-24 15:09:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8344kb
  • [2023-09-24 15:09:12]
  • 提交

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'