QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187217#3854. Radarwind_whisper#WA 2ms6296kbC++141.2kb2023-09-24 15:34:462023-09-24 15:34:46

Judging History

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

  • [2023-09-24 15:34:46]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6296kb
  • [2023-09-24 15:34:46]
  • 提交

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'