QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187159 | #3854. Radar | dfsaab# | WA | 88ms | 4980kb | C++14 | 1.5kb | 2023-09-24 15:01:54 | 2023-09-24 15:01:55 |
Judging History
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'