QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194908 | #3854. Radar | realcomplex0# | TL | 5ms | 3828kb | C++20 | 2.4kb | 2023-09-30 23:31:33 | 2023-09-30 23:31:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
vector<ld> radii;
set<ld> ang;
ld calc(ld x, ld y, ld an, ld rad){
ld xi = sin(an) * rad;
ld yi = cos(an) * rad;
return (x - xi) * (x - xi) + (y - yi) * (y - yi);
}
int main(){
fastIO;
//freopen("in_a.txt", "r", stdin);
int r, f, n;
cin >> r >> f >> n;
ld rr;
for(int i = 0 ; i < r; i ++ ){
cin >> rr;
radii.push_back(rr);
}
sort(radii.begin(), radii.end());
ld x, y;
for(int i = 0 ; i < f; i ++ ){
cin >> x >> y;
ang.insert(atan2(x,y));
}
ld cur_ang;
ld res;
int lf, rf;
int cl, cr;
for(int iq = 0 ; iq < n; iq ++ ){
cin >> x >> y;
cur_ang = atan2(x, y);
auto it = ang.upper_bound(cur_ang);
auto pv = it;
res = (ld)1e18;
for(int iter = 0; iter < 2; iter ++ ){
lf = 0;
rf = r - 1;
while(lf + 2 < rf){
cl = (lf + lf + rf) / 3;
cr = (lf + rf + rf) / 3;
if(calc(x, y, *it, radii[cl]) < calc(x, y, *it, radii[cr])){
rf = cr;
}
else{
lf = cl;
}
}
for(int i = lf; i <= rf; i ++ ){
res = min(res, calc(x, y, *it, radii[i]));
}
it ++ ;
if(it == ang.end()){
it = ang.begin();
}
}
for(int iter = 0; iter < 2; iter ++ ){
if(pv == ang.begin()){
pv = ang.end();
}
pv -- ;
lf = 0;
rf = r - 1;
while(lf + 2 < rf){
cl = (lf + lf + rf) / 3;
cr = (lf + rf + rf) / 3;
if(calc(x, y, *pv, radii[cl]) < calc(x, y, *pv, radii[cr])){
rf = cr;
}
else{
lf = cl;
}
}
for(int i = lf; i <= rf; i ++ ){
res = min(res, calc(x, y, *pv, radii[i]));
}
}
cout << fixed << setprecision(8) << sqrt(res) << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
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.60529107 0.97777229 1.55184511 1.41421356
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3716kb
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.87498510 15.87498510 15.87498510 15.87498510 15.87498510 15.87498510 15.87498510 15.87498510 4.92965670 4.92965670 4.92965670 4.92965670 4.92965670 4.92965670 4.92965670 4.92965670 2.00000000 2.00000000 2.00000000 2.00000000 0.07106781 0.07106781 0.07106781 0.07106781 2.00000000 2.00000000 2.0000...
result:
ok 32 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
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.05538514 4.12310563 3.60555128 11.04536102 15.29705854 1.41421356 8.24621125 7.00000000 8.94427191 3.00000000 12.16552506 5.00000000 5.09901951 11.18033989 1.41421356 2.00000000 2.00000000 3.00000000 3.16227766 8.24621125 4.47213595 5.00000000 8.54400375 9.00000000 19.41648784 2.23606798 3.6055512...
result:
ok 1681 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 3704kb
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.77737212 4.63159368 6.89565610 12.29142291 6.55596400 4.27030421 4.39253600 6.36782589 6.55596400 2.99031638 10.18752036 2.83362617 2.97706483 4.69677986 4.35223989 11.32845581 3.38403015 1.83645937 2.94725152 7.63513190 9.09218467 8.02697478 5.72755681 10.73846242 2.67892208 7.86903994 2.6606535...
result:
ok 1681 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3768kb
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.00000000 4.00000000 4.00000000 4.00000000 5.00000000 5.00000000 5.00000000 5.00000000 1.00000000 1.00000000 1.00000000 1.00000000 8.06225775 8.06225775 8.06225775 8.06225775
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
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.00000000 2.00000000 4.00000000 8.00000000 16.00000000 32.00000000 64.00000000 128.00000000 256.00000000 512.00000000 1024.00000000 2048.00000000 4096.00000000 8192.00000000 16384.00000000 32768.00000000 65536.00000000 131072.00000000 262144.00000000 524288.00000000 1047.00047755 2095.00023866 4190...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 3828kb
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.39307160 16.45344124 14.47564009 19.04323137 16.18293242 19.04323137 19.01057654 3.30589355 11.76318762 14.66730836 16.29552564 7.61770551 16.69265290 25.87005769 16.18293220 20.08487043 10.69451168 19.29511601 23.75926188 19.33616564 17.38477631 6.42433455 18.10569617 15.61689155 6.42433510 4.012...
result:
ok 1681 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3716kb
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.00000000 3.00000000 2.00000000 1.00000000 0.00000000 1.00000000 2.00000000 1.00000000 0.00000000 1.00000000 2.00000000 3.00000000 4.00000000 3.00000000 2.00000000 1.00000000 0.00000000 1.00000000 2.00000000 3.00000000 4.00000000 3.00000000 2.00000000 1.00000000 0.00000000 1.00000000 2.00000000 1.0...
result:
ok 108 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3772kb
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.21954446 3.16227766 15.03329638 6.70820393 6.00000000 19.10497317 12.00000000 1.00000000 5.65685425 4.12310563 1.41421356 5.09901951 12.36931688 19.23538406 6.00000000 9.48683298 6.32455532 4.12310563 18.02775638 4.47213595 13.34166406 2.23606798 13.15294644 7.07106781 7.28010989 3.00000000 11.045...
result:
ok 1681 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3772kb
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.41421356 18.43908891 4.47213595 12.04159458 14.31782106 10.44030651 19.02629759 15.03329638 3.60555128 8.54400375 18.02775638 17.46424920 20.00000000 5.00000000 13.34166406 10.04987562 18.02775638 16.00000000 1.41421356 19.10497317 17.00000000 12.16552506 10.04987562 9.84885780 13.15294644 11.7046...
result:
ok 1681 numbers
Test #11:
score: 0
Accepted
time: 5ms
memory: 3816kb
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.34166797 7.61577311 19.23539988 17.26268044 14.14213562 18.02776437 10.19804688 11.70469991 6.00000000 16.03121954 14.03567684 3.00000000 7.28012529 20.09975124 14.14213959 13.00000000 16.27880485 4.47213595 8.94427191 5.00000000 2.00000000 18.24828759 15.52417470 4.99999039 13.15293061 14.560219...
result:
ok 1681 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 2 1 1 2 4 0 1 0 -1 -7 0
output:
7.07106781
result:
ok found '7.0710678', expected '7.0710678', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
3 2 1 1 2 4 0 1 -1 -999001 -7 0
output:
7.07106682
result:
ok found '7.0710668', expected '7.0710668', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3716kb
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.00000000 0.00000000 1.00000000 0.00000000 1.00000000 2.00000000 1.00000000 0.00000000 1.00000000 2.00000000 3.00000000 4.00000000 5.00000000 6.00000000 7.00000000 8.00000000 9.00000000 10.00000000 1.41421356 2.23606798 3.16227766 4.12310563 5.09901951 6.08276253 7.07106781 8.06225775 9.05538514 1....
result:
ok 36 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3736kb
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.31827319 3.14737924 3.04300366 5.60113966 6.29475848 6.55343850 6.08600733 7.48016453
result:
ok 8 numbers
Test #16:
score: -100
Time Limit Exceeded
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.99886579 14.52542302 21.07310212 31.84318911 115.92489501 49.99139105 60.50662972 69.95813004 134.90230815 90.17256143 100.22015141 110.15485289 119.83813806 169.25925992 139.85771381 149.90386261 159.81303402 169.92400891 209.99705092 189.71365104 199.62297502 209.78857266 219.72774753 229.76351...