QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187482#3854. Radarszhlg#WA 2ms6440kbC++142.2kb2023-09-24 17:43:392023-09-24 17:43:40

Judging History

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

  • [2023-09-24 17:43:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6440kb
  • [2023-09-24 17:43:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int f = 1,x = 0;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
int r,f,n;
const int maxn = 400015;
const double eps = 1e-9;
double a1[maxn];
double a2[maxn];
double pi = acos(-1);
double js(double x1,double x2,double x3,double x4){
	double x5 = x3 * cos(x4);
	double x6 = x3 * sin(x4);
	x1 = x1 - x5;
	x2 = x2 - x6;
	return sqrt(x1 * x1 + x2 * x2);
}
signed main()
{
	r = read(),f = read(),n = read();
	for(int i=1;i<=r;++i){
		int x = read();
		a1[i] = 1.0 * x;
	}
	sort(a1 + 1,a1 + r + 1);
	for(int i=1;i<=f;++i){
		int x = read(),y = read();
		if(x == 0){
			if(y > 0) a2[i] = pi/2;
			else a2[i] = -pi/2;
		}
		else
		{
			double qaq = 1.0 * y / x;
			if(x > 0) a2[i] = atan(qaq);
			else{
				if(y <= 0) a2[i] = atan(qaq) - pi;
				else a2[i] = atan(qaq) + pi;
			}
		}
	}
	for(int i=1;i<=f;++i) a2[i+f] = a2[i] + 2 * pi;
	for(int i=1;i<=f;++i) a2[i + 2 * f] = a2[i] - 2 * pi;
	sort(a2 + 1,a2 + 3 * f + 1);
	f = 3 * f;
//	for(int i=1;i<=f;++i) printf("%lf ",a2[i]);
	while(n != 0){
		--n;
		int x = read(),yyy = read();
		double x1 = 1.0 * x,y1 = 1.0 * yyy;
		double r1 = sqrt(x1 * x1 + y1 * y1);
		//l,l - 1
		double r2,r3;
		if(x == 0){
			if(yyy > 0) r2 = pi/2;
			else r2 = -pi/2;
		}
		else{
			r3 = 1.0 * y1 / x1;
			if(x > 0) r2 = atan(r3);
			else
			{
				if(yyy <= 0) r2 = atan(r3) - pi;
				else r2 = atan(r3) + pi;
			}
		}
		int zz = 1,yy = f;
		while(zz <= yy){
			int mid = (zz+yy)>>1;
			if(a2[mid] < r2) zz = mid + 1;
			else yy = mid - 1;
		}
		//l,l - 1
		double ans = 1e12;
		//printf("%lld %lld\n",z,z-1);
		for(int j=min(zz+1,f);j>=max(zz-2,1ll);--j){
			double rr1 = fabs(r1 * cos(r2 - a2[j]));
			int z = 1,y = r;
			while(z <= y){
				int mid = (z+y)>>1;
				if(a1[mid] < rr1) z = mid + 1;
				else y = mid - 1;
			}
		//	printf("%lf %lld %lf\n",a2[j],z,r2);
			for(int i=min(z+1,r);i>=max(z-2,1ll);--i){
				ans = min(ans,js(x1,y1,a1[i],a2[j]));
			}
			//printf("?");
		}
		printf("%.12lf\n",ans);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6440kb

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: 1ms
memory: 6340kb

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: 2ms
memory: 6336kb

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: 2ms
memory: 6212kb

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.990316379370
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: 6420kb

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: 0
Accepted
time: 0ms
memory: 6356kb

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.000000000000
2048.000000000000
4096.000000000000
8191.999999999999
16383.999999999998
32767.999999999996
65535.999999999993
131071.99999...

result:

ok 120 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 6376kb

input:

4 4 1681
1000
1
999000
999
999000 999000
-999001 999000
999000 -999001
-999001 -999001
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18...

output:

8.393071595900
16.453441243477
14.475640085236
19.043231368144
16.182932417451
19.043231368144
19.010576536590
3.305893553661
11.763187620795
14.667308360056
16.295525639797
7.617705510948
16.692652903019
25.870057685089
16.182932198760
20.084870431585
10.694511684541
19.295116007469
23.759261884935...

result:

ok 1681 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 6316kb

input:

3 3 108
8
16
4
0 1
0 -1
-1 0
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
0 -8
0 -9
0 -10
0 -11
0 -12
0 -13
0 -14
0 -15
0 -16
0 -17
0 -18
0 -19
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16...

output:

4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
...

result:

ok 108 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 6348kb

input:

3 3 1681
8
16
4
-1 0
0 1
0 -1
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18 7
6 -3
-9 -9
-8 -12
-16 20
-1 -13
14 20
-7 -14
13 -14
19...

output:

9.219544457293
3.162277660168
15.033296378373
6.708203932499
6.000000000000
19.104973174543
12.000000000000
1.000000000000
5.656854249492
4.123105625618
1.414213562373
5.099019513593
12.369316876853
19.235384061671
6.000000000000
9.486832980505
6.324555320337
4.123105625618
18.027756377320
4.4721359...

result:

ok 1681 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 6324kb

input:

3 2 1681
16
8
4
0 1
0 -1
-1 -17
-18 -12
4 -6
12 17
-14 -11
-10 19
-19 -15
-15 -17
2 13
-8 -13
-18 7
-17 12
-20 16
3 12
-13 13
10 5
18 -9
-16 4
1 17
-19 -6
-17 -4
12 -18
-10 -17
-9 -20
13 6
11 0
4 5
2 -15
8 -12
1 9
17 -10
1 -13
-8 1
-12 11
5 0
20 -16
-5 8
-13 -2
7 12
-8 14
-4 9
10 -11
19 -3
-18 8
-4 ...

output:

1.414213562373
18.439088914586
4.472135955000
12.041594578792
14.317821063276
10.440306508911
19.026297590440
15.033296378373
3.605551275464
8.544003745318
18.027756377320
17.464249196573
20.000000000000
5.000000000000
13.341664064126
10.049875621121
18.027756377320
16.000000000000
1.414213562373
19...

result:

ok 1681 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 6288kb

input:

3 2 1681
16
8
4
-1 -999001
0 1
13 -1
-7 19
19 -13
17 -1
-14 14
18 -9
10 -10
11 20
6 16
-16 7
14 -7
-3 4
7 -14
-20 2
14 -6
13 16
-16 -13
2 0
-8 20
-3 20
0 14
-18 1
-15 12
-3 -12
-13 -14
14 0
12 4
-14 9
-10 -9
20 15
-20 0
19 4
16 -8
3 -14
19 -15
-11 19
6 -9
-17 -5
-17 13
18 12
6 12
-16 -10
12 7
8 -6
-...

output:

13.341667965588
7.615773105864
19.235399881682
17.262680444705
14.142135623731
18.027764372991
10.198046879677
11.704699910720
6.000000000000
16.031219541881
14.035676835267
3.000000000000
7.280125289047
20.099751242242
14.142139587489
13.000000000000
16.278804854418
4.472135955000
8.944271909999
5....

result:

ok 1681 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 6340kb

input:

3 2 1
1
2
4
0 1
0 -1
-7 0

output:

7.071067811865

result:

ok found '7.0710678', expected '7.0710678', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 6248kb

input:

3 2 1
1
2
4
0 1
-1 -999001
-7 0

output:

7.071066820926

result:

ok found '7.0710668', expected '7.0710668', error '0.0000000'

Test #14:

score: -100
Wrong Answer
time: 1ms
memory: 6212kb

input:

4 1 36
8
1
2
4
0 1
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
0 -8
0 -9
-1 0
-2 0
-3 0
-4 0
-5 0
-6 0
-7 0
-8 0
-9 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0

output:

0.000000000000
0.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
5.000000000000
7.000000000000
8.000000000000
9.000000000000
10.000000000000
13.000000000000
1.414213562373
2.23606797750...

result:

wrong answer 14th numbers differ - expected: '6.0000000', found: '7.0000000', error = '0.1666667'