QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187167#3854. Radardoll_sister#WA 7ms6096kbC++141.2kb2023-09-24 15:04:152023-09-24 15:04:15

Judging History

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

  • [2023-09-24 15:04:15]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:6096kb
  • [2023-09-24 15:04:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,q;
long double dist[N];
long double deg[N];
inline pair<long double,long double>getdot(long double dis,long double deg){
	return make_pair(cosl(deg)*dis,sinl(deg)*dis);
}
void work(){
	long double ans=1e100;
	int x,y;
	cin>>x>>y;
	vector<long double>Di,De;
	long double D=hypotl(x,y),ang=atan2l(y,x);
	int it=lower_bound(deg+1,deg+m+1,atan2l(y,x))-deg;
	for(int i=-3;i<=3;i++){
		long double w=fabsl(cosl(ang-deg[(it+i+m)%m+1])*D);
		int p=lower_bound(dist+1,dist+n+1,w)-dist;
		for(int j=-3;j<=3;j++){
			if(p+j>=1&&p+j<=n){
				auto res=getdot(dist[p+j],deg[(it+i+m)%m+1]);
				ans=min(ans,hypotl(res.first-x,res.second-y));
			}
		}
	}
	for(auto d:Di)
	for(auto g:De){
		auto res=getdot(d,g);
		ans=min(ans,hypotl(res.first-x,res.second-y));
	}
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cout<<fixed<<setprecision(11);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i)
	cin>>dist[i];
	dist[++n]=1e8;
	sort(dist+1,dist+n+1);
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		deg[i]=atan2l(y,x);
	}
	sort(deg+1,deg+m+1);
	for(;q--;)work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107292
0.97777229047
1.55184510540
1.41421356237

result:

ok 4 numbers

Test #2:

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

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.87498509926
15.87498509926
15.87498509926
15.87498509926
15.87498509926
15.87498509926
15.87498509926
15.87498509926
4.92965670105
4.92965670105
4.92965670105
4.92965670105
4.92965670105
4.92965670105
4.92965670105
4.92965670105
2.00000000000
2.00000000000
2.00000000000
2.00000000000
0.0710678118...

result:

ok 32 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 5960kb

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.05538513814
4.12310562562
3.60555127546
11.04536101719
15.29705854078
1.41421356237
8.24621125124
7.00000000000
8.94427191000
3.00000000000
12.16552506060
5.00000000000
5.09901951359
11.18033988750
1.41421356237
2.00000000000
2.00000000000
3.00000000000
3.16227766017
8.24621125124
4.47213595500
5....

result:

ok 1681 numbers

Test #4:

score: 0
Accepted
time: 6ms
memory: 6096kb

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.77737211930
4.63159368259
6.89565610098
12.29142290537
6.55596400358
4.27030420605
4.39253600045
6.36782588575
6.55596400358
2.99031637937
10.18752035950
2.83362616651
2.97706483137
4.69677986016
4.35223988869
11.32845580980
3.38403014771
1.83645936574
2.94725151642
7.63513189585
9.09218466976
8....

result:

ok 1681 numbers

Test #5:

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

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.00000000000
4.00000000000
4.00000000000
4.00000000000
5.00000000000
5.00000000000
5.00000000000
5.00000000000
1.00000000000
1.00000000000
1.00000000000
1.00000000000
8.06225774830
8.06225774830
8.06225774830
8.06225774830

result:

ok 16 numbers

Test #6:

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

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.00000000000
2.00000000000
4.00000000000
8.00000000000
16.00000000000
32.00000000000
64.00000000000
128.00000000000
256.00000000000
512.00000000000
1024.00000000000
2048.00000000000
4096.00000000000
8192.00000000000
16384.00000000000
32768.00000000000
65536.00000000000
131072.00000000000
262144.000...

result:

ok 120 numbers

Test #7:

score: 0
Accepted
time: 7ms
memory: 6084kb

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.39307159590
16.45344124348
14.47564008524
19.04323136814
16.18293241745
19.04323136814
19.01057653659
3.30589355366
11.76318762080
14.66730836006
16.29552563980
7.61770551095
16.69265290302
25.87005768509
16.18293219876
20.08487043158
10.69451168454
19.29511600747
23.75926188494
19.33616563923
17....

result:

ok 1681 numbers

Test #8:

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

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.00000000000
3.00000000000
2.00000000000
1.00000000000
0.00000000000
1.00000000000
2.00000000000
1.00000000000
0.00000000000
1.00000000000
2.00000000000
3.00000000000
4.00000000000
3.00000000000
2.00000000000
1.00000000000
0.00000000000
1.00000000000
2.00000000000
3.00000000000
4.00000000000
3.0000...

result:

ok 108 numbers

Test #9:

score: 0
Accepted
time: 3ms
memory: 5932kb

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.21954445729
3.16227766017
15.03329637837
6.70820393250
6.00000000000
19.10497317454
12.00000000000
1.00000000000
5.65685424949
4.12310562562
1.41421356237
5.09901951359
12.36931687685
19.23538406167
6.00000000000
9.48683298051
6.32455532034
4.12310562562
18.02775637732
4.47213595500
13.34166406413...

result:

ok 1681 numbers

Test #10:

score: 0
Accepted
time: 6ms
memory: 5960kb

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.41421356237
18.43908891459
4.47213595500
12.04159457879
14.31782106328
10.44030650891
19.02629759044
15.03329637837
3.60555127546
8.54400374532
18.02775637732
17.46424919657
20.00000000000
5.00000000000
13.34166406413
10.04987562112
18.02775637732
16.00000000000
1.41421356237
19.10497317454
17.000...

result:

ok 1681 numbers

Test #11:

score: 0
Accepted
time: 6ms
memory: 6032kb

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.34166796559
7.61577310586
19.23539988168
17.26268044471
14.14213562373
18.02776437299
10.19804687968
11.70469991072
6.00000000000
16.03121954188
14.03567683527
3.00000000000
7.28012528905
20.09975124224
14.14213958749
13.00000000000
16.27880485442
4.47213595500
8.94427191000
5.00000000000
2.00000...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781187

result:

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

Test #13:

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

input:

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

output:

7.07106682093

result:

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

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 5948kb

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.00000000000
0.00000000000
1.00000000000
0.00000000000
1.00000000000
2.00000000000
1.00000000000
0.00000000000
1.00000000000
2.00000000000
3.00000000000
4.00000000000
5.00000000000
6.00000000000
7.00000000000
8.00000000000
9.00000000000
11.00000000000
1.41421356237
2.23606797750
3.16227766017
4.123...

result:

wrong answer 18th numbers differ - expected: '10.0000000', found: '11.0000000', error = '0.1000000'