QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187560#3854. RadarNax_hueuxWA 1ms2516kbC++142.4kb2023-09-24 18:04:392023-09-24 18:04:40

Judging History

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

  • [2023-09-24 18:04:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:2516kb
  • [2023-09-24 18:04:39]
  • 提交

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'