QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194949 | #3854. Radar | realcomplex0# | WA | 4ms | 3960kb | C++14 | 2.6kb | 2023-09-30 23:52:55 | 2023-09-30 23:52:55 |
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 si;
ld co;
ld calc(ld x, ld y, ld rad){
ld xi = si * rad;
ld yi = co * rad;
return (x - xi) * (x - xi) + (y - yi) * (y - yi);
}
int main(){
fastIO;
//freopen("big.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 cur;
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 < 1; iter ++ ){
cur = *it;
si = sin(cur);
co = cos(cur);
lf = 0;
rf = r - 1;
while(lf + 2 < rf){
cl = (lf + lf + rf) / 3;
cr = (lf + rf + rf) / 3;
if(calc(x, y, radii[cl]) < calc(x, y, radii[cr])){
rf = cr;
}
else{
lf = cl;
}
}
for(int i = lf; i <= rf; i ++ ){
res = min(res, calc(x, y, radii[i]));
}
it ++ ;
if(it == ang.end()){
it = ang.begin();
}
}
for(int iter = 0; iter < 1; iter ++ ){
if(pv == ang.begin()){
pv = ang.end();
}
pv -- ;
cur = *pv;
si = sin(cur);
co = cos(cur);
lf = 0;
rf = r - 1;
while(lf + 2 < rf){
cl = (lf + lf + rf) / 3;
cr = (lf + rf + rf) / 3;
if(calc(x, y, radii[cl]) < calc(x, y, radii[cr])){
rf = cr;
}
else{
lf = cl;
}
}
for(int i = lf; i <= rf; i ++ ){
res = min(res, calc(x, y, 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: 3936kb
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: 0ms
memory: 3888kb
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: 2ms
memory: 3960kb
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: 2ms
memory: 3956kb
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: 3880kb
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: 3776kb
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: 3844kb
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: 3932kb
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: 2ms
memory: 3936kb
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: 3956kb
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: -100
Wrong Answer
time: 4ms
memory: 3940kb
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.92838828 7.61577311 25.49509757 17.72004515 14.14213562 22.20360331 17.20465053 11.70469991 6.00000000 16.03121954 17.80449381 3.00000000 19.31320792 20.09975124 17.20465053 13.00000000 16.27880485 4.47213595 8.94427191 5.00000000 2.00000000 18.24828759 15.52417470 4.99999039 13.15293061 14.56021...
result:
wrong answer 1st numbers differ - expected: '13.3416680', found: '13.9283883', error = '0.0439765'