QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187159#3854. Radardfsaab#WA 88ms4980kbC++141.5kb2023-09-24 15:01:542023-09-24 15:01:55

Judging History

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

  • [2023-09-24 15:01:55]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:4980kb
  • [2023-09-24 15:01:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define double long double
typedef long long ll;
const int N=1e5+5;
int n,m;
ll mul(ll x1,ll y1,ll x2,ll y2){
	return x1*y2-x2*y1;	
}
ll pmul(ll x1,ll y1,ll x2,ll y2){
	return x1*x2+y1*y2;
}
double getlen(ll x,ll y){
	return sqrt(x*x+y*y);
}
struct Line{
	int x,y;
	Line(){}
	Line(int a,int b){x=a,y=b;}
	bool bel(){
		if((x>0&&y>=0)||(x<=0&&y>0)) return 0;
		return 1; 	
	}
	bool operator < (Line c) {
		if(bel()!=c.bel()) return bel()<c.bel();
		return mul(x,y,c.x,c.y)>=0;
	}
}f[N];
int r[N];
inline double calc(Line a,Line b){
	double d=pmul(a.x,a.y,b.x,b.y)/getlen(b.x,b.y);
	double l=getlen(a.x,a.y);
	int p = lower_bound(r+1,r+n+1,d) - r;
	//cout<<p<<' '<<l<<' '<<d<<endl;
	double ans=1e18;
	for(int i=max(p-1,1);i<=p+1&&i<=n;i++){
		ans=min(ans,sqrt(l*l+1.0*r[i]*(r[i]-2.0*d)));
	}
	return ans;
}
int main(){
	int T;
	scanf("%d%d%d",&n,&m,&T);
	for(int i=1;i<=n;i++) scanf("%d",&r[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&f[i].x,&f[i].y);
	}	
	sort(f+1,f+m+1);
	sort(r+1,r+n+1);
	while(T--){
		Line u;
		scanf("%d%d",&u.x,&u.y);
		int p = lower_bound(f+1,f+m+1,u) - f;
		//cout<<calc(u,f[7])<<endl;
		//cout<<p<<' '<<f[p].x<<' '<<f[p].y<<endl;
		double ans=1e18;
		for(int i=p-2;i<=p+2;i++){
			int c=i;
			while(c<1) c+=m;
			while(c>m) c-=m;
			ans=min(ans,calc(u,f[c]));
		}
		printf("%.10Lf\n",ans);
	}
	return 0;	
}
/*
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: 3856kb

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.6052910729
0.9777722905
1.5518451054
1.4142135624

result:

ok 4 numbers

Test #2:

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

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.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
2.0000000000
2.0000000000
2.0000000000
2.0000000000
0.0710678119
0.0710678119
0.0710...

result:

ok 32 numbers

Test #3:

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

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.0553851381
4.1231056256
3.6055512755
11.0453610172
15.2970585408
1.4142135624
8.2462112512
7.0000000000
8.9442719100
3.0000000000
12.1655250606
5.0000000000
5.0990195136
11.1803398875
1.4142135624
2.0000000000
2.0000000000
3.0000000000
3.1622776602
8.2462112512
4.4721359550
5.0000000000
8.54400374...

result:

ok 1681 numbers

Test #4:

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

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.7773721193
4.6315936826
6.8956561010
12.2914229054
6.5559640036
4.2703042060
4.3925360004
6.3678258857
6.5559640036
2.9903163794
10.1875203595
2.8336261665
2.9770648314
4.6967798602
4.3522398887
11.3284558098
3.3840301477
1.8364593657
2.9472515164
7.6351318958
9.0921846698
8.0269747761
5.72755681...

result:

ok 1681 numbers

Test #5:

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

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.0000000000
4.0000000000
4.0000000000
4.0000000000
5.0000000000
5.0000000000
5.0000000000
5.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
8.0622577483
8.0622577483
8.0622577483
8.0622577483

result:

ok 16 numbers

Test #6:

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

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.0000000000
2.0000000000
4.0000000000
8.0000000000
16.0000000000
32.0000000000
64.0000000000
128.0000000000
256.0000000000
512.0000000000
1024.0000000000
2048.0000000000
4096.0000000000
8192.0000000000
16384.0000000000
32768.0000000000
65536.0000000000
131072.0000000000
262144.0000000000
524288.000...

result:

ok 120 numbers

Test #7:

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

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.3930715959
16.4534412435
14.4756400852
19.0432313681
16.1829324175
19.0432313681
19.0105765366
3.3058935537
11.7631876208
14.6673083601
16.2955256398
7.6177055109
16.6926529030
25.8700576851
16.1829321988
20.0848704316
10.6945116845
19.2951160075
23.7592618849
19.3361656392
17.3847763109
6.4243345...

result:

ok 1681 numbers

Test #8:

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

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.0000000000
3.0000000000
2.0000000000
1.0000000000
0.0000000000
1.0000000000
2.0000000000
1.0000000000
0.0000000000
1.0000000000
2.0000000000
3.0000000000
4.0000000000
3.0000000000
2.0000000000
1.0000000000
0.0000000000
1.0000000000
2.0000000000
3.0000000000
4.0000000000
3.0000000000
2.0000000000
1...

result:

ok 108 numbers

Test #9:

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

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.2195444573
3.1622776602
15.0332963784
6.7082039325
6.0000000000
19.1049731745
12.0000000000
1.0000000000
5.6568542495
4.1231056256
1.4142135624
5.0990195136
12.3693168769
19.2353840617
6.0000000000
9.4868329805
6.3245553203
4.1231056256
18.0277563773
4.4721359550
13.3416640641
2.2360679775
13.1529...

result:

ok 1681 numbers

Test #10:

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

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.4142135624
18.4390889146
4.4721359550
12.0415945788
14.3178210633
10.4403065089
19.0262975904
15.0332963784
3.6055512755
8.5440037453
18.0277563773
17.4642491966
20.0000000000
5.0000000000
13.3416640641
10.0498756211
18.0277563773
16.0000000000
1.4142135624
19.1049731745
17.0000000000
12.165525060...

result:

ok 1681 numbers

Test #11:

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

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.3416679656
7.6157731059
19.2353998817
17.2626804447
14.1421356237
18.0277643730
10.1980468797
11.7046999107
6.0000000000
16.0312195419
14.0356768353
3.0000000000
7.2801252890
20.0997512422
14.1421395875
13.0000000000
16.2788048544
4.4721359550
8.9442719100
5.0000000000
2.0000000000
18.2482875909
...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.0710678119

result:

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

Test #13:

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

input:

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

output:

7.0710668209

result:

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

Test #14:

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

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.0000000000
0.0000000000
1.0000000000
0.0000000000
1.0000000000
2.0000000000
1.0000000000
0.0000000000
1.0000000000
2.0000000000
3.0000000000
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
1.4142135624
2.2360679775
3.1622776602
4.1231056256
5.0990195136
...

result:

ok 36 numbers

Test #15:

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

input:

4 5 8
8
1
2
4
0 1
1 1
1 -1
-3 2
-2 -5
-4 0
-4 -1
-4 -2
-8 -1
-8 -2
-8 -3
-8 -4
-9 -3

output:

2.3182731895
3.1473792392
3.0430036646
5.6011396576
6.2947584784
6.5534384969
6.0860073291
7.4801645331

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 86ms
memory: 4980kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.9988657019
14.5254230188
21.0731021178
31.8431891132
115.9248950136
49.9913910549
60.5066297164
69.9581300396
134.9023081512
90.1725614314
100.2201514117
110.1548528851
119.8381380577
169.2592599248
139.8577138100
149.9038626121
159.8130340193
169.9240089130
209.9970509223
189.7136510355
199.6229...

result:

ok 99999 numbers

Test #17:

score: -100
Wrong Answer
time: 88ms
memory: 4800kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.0000000000
15.2958413090
21.4720815032
30.8393085198
35.0065552725
50.9314581075
60.5066198290
70.3637954422
80.0070389371
90.0561713216
100.0006332931
110.0505082798
119.8381280857
129.8851979893
134.8680764762
149.8338746363
159.9504696769
169.9239989400
174.7854552073
189.6294162543
199.660469...

result:

wrong answer 50045th numbers differ - expected: '2.4915616', found: '2.4915542', error = '0.0000030'