QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#880766 | #3854. Radar | ychangseok | TL | 12ms | 4352kb | C++17 | 2.9kb | 2025-02-03 19:49:24 | 2025-02-03 19:49:24 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double lb;
#define all(v) v.begin(), v.end()
#define M_PI 3.14159265358979323846
#define EPS 1e-6
lb getdist(ll x, ll y, ll r, lb a){
// cout << r * cos(a) << ' ' << r * sin(a) << ' ';
a *= M_PI / 180;
lb dx = x - r * cos(a);
lb dy = y - r * sin(a);
return dx*dx + dy*dy;
}
ll n, m, q;
ll x, y, r;
vector<ll> vr;
vector<lb> angle;
int main(){
cin.tie(0)->sync_with_stdio(0);
cout << fixed;
cout.precision(12);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++){
cin >> r;
vr.push_back(r);
}
for (int i = 1; i <= m; i++){
cin >> x >> y;
angle.push_back(atan2(y,x) * 180 / M_PI);
}
sort(all(vr));
sort(all(angle));
vector<lb> tmp;
for (int i = 0; i < m; i++){
tmp.push_back(angle[i] - 360);
}
for (int i = 0; i < m; i++){
tmp.push_back(angle[i]);
}
for (int i = 0; i < m; i++){
tmp.push_back(angle[i] + 360);
}
// for (int i = 0; i < n; i++){
// cout << vr[i] << ' ';
// }
// cout << endl;
// for (int i = 0; i < m; i++){
// cout << angle[i] * 180 / M_PI << endl;
// // if (i % m == m-1) cout << endl;
// }
// cout << endl;
// for (int i = 0; i < 3*m; i++){
// cout << tmp[i] * 180 / M_PI << endl;
// if (i % m == m-1) cout << endl;
// }
// cout << endl;
// cout << endl;
while (q--){
cin >> x >> y;
int left = 0;
int right = n - 1;
while (left < right){
int mid = (left + right + 1) / 2;
if (x*x+y*y >= vr[mid]*vr[mid]){
left = mid;
}else{
right = mid - 1;
}
}
// cout << x << ' ' << y << ' ' << vr[left] << '\n';
int lr = left;
lb theta = atan2(y, x) * 180 / M_PI;
int lt = 0;
left = 0;
right = 3*m - 1;
while (left+1 < right){
int mid = (left + right + 1) / 2;
if (tmp[mid] > theta + EPS) right = mid - 1;
else left = mid;
}
// cout << angle[left].deg << ' ' << theta << ' ' << angle[right].deg << endl;
lt = left;
// cout << lt << ' ' << rt << endl;
lb dist = 9e18;
for (int ridx = lr-5; ridx <= lr+5; ridx++){
if (ridx < 0) continue;
if (ridx >= n) continue;
for (int tidx = lt-5; tidx <= lt+5; tidx++){
if (tidx < 0) continue;
lb d = getdist(x, y, vr[ridx], angle[(tidx)%m]);
// cout << d << endl;
dist = min(dist, d);
}
}
cout << sqrt(dist) << '\n';
// cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4352kb
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.605291072917 0.977772290466 1.551845105402 1.414213562373
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 4224kb
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.874985099258 15.874985099258 15.874985099258 15.874985099258 15.874985099258 15.874985099258 15.874985099258 15.874985099258 4.929656701046 4.929656701046 4.929656701046 4.929656701046 4.929656701046 4.929656701046 4.929656701046 4.929656701046 2.000000000000 2.000000000000 2.000000000000 2.00000...
result:
ok 32 numbers
Test #3:
score: 0
Accepted
time: 8ms
memory: 4352kb
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.055385138137 4.123105625618 3.605551275464 11.045361017187 15.297058540778 1.414213562373 8.246211251235 7.000000000000 8.944271909999 3.000000000000 12.165525060596 5.000000000000 5.099019513593 11.180339887499 1.414213562373 2.000000000000 2.000000000000 3.000000000000 3.162277660168 8.246211251...
result:
ok 1681 numbers
Test #4:
score: 0
Accepted
time: 6ms
memory: 4352kb
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.777372119304 4.631593682590 6.895656100977 12.291422905367 6.555964003581 4.270304206047 4.392536000448 6.367825885745 6.555964003581 2.990316379371 10.187520359495 2.833626166509 2.977064831365 4.696779860162 4.352239888693 11.328455809797 3.384030147710 1.836459365744 2.947251516416 7.635131895...
result:
ok 1681 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 4352kb
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.000000000000 4.000000000000 4.000000000000 4.000000000000 5.000000000000 5.000000000000 5.000000000000 5.000000000000 1.000000000000 1.000000000000 1.000000000000 1.000000000000 8.062257748299 8.062257748299 8.062257748299 8.062257748299
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 4352kb
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.000000000000 2.000000000000 4.000000000000 8.000000000000 16.000000000000 32.000000000000 64.000000000000 128.000000000000 256.000000000000 512.000000000000 1024.000000000000 2048.000000000000 4096.000000000000 8192.000000000000 16383.999999999999 32767.999999999998 65535.999999999997 131071.99999...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 12ms
memory: 4352kb
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.393071595900 16.453441243477 14.475640085236 19.043231368144 16.182932417451 19.043231368144 19.010576536590 3.305893553661 11.763187620795 14.667308360056 16.295525639797 7.617705510948 16.692652903019 25.870057685089 16.182932198760 20.084870431585 10.694511684541 19.295116007469 23.759261884935...
result:
ok 1681 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 4352kb
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.000000000000 3.000000000000 2.000000000000 1.000000000000 0.000000000000 1.000000000000 2.000000000000 1.000000000000 0.000000000000 1.000000000000 2.000000000000 3.000000000000 4.000000000000 3.000000000000 2.000000000000 1.000000000000 0.000000000000 1.000000000000 2.000000000000 3.000000000000 ...
result:
ok 108 numbers
Test #9:
score: 0
Accepted
time: 9ms
memory: 4352kb
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.219544457293 3.162277660168 15.033296378373 6.708203932499 6.000000000000 19.104973174543 12.000000000000 1.000000000000 5.656854249492 4.123105625618 1.414213562373 5.099019513593 12.369316876853 19.235384061671 6.000000000000 9.486832980505 6.324555320337 4.123105625618 18.027756377320 4.4721359...
result:
ok 1681 numbers
Test #10:
score: 0
Accepted
time: 9ms
memory: 4352kb
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.414213562373 18.439088914586 4.472135955000 12.041594578792 14.317821063276 10.440306508911 19.026297590440 15.033296378373 3.605551275464 8.544003745318 18.027756377320 17.464249196573 20.000000000000 5.000000000000 13.341664064126 10.049875621121 18.027756377320 16.000000000000 1.414213562373 19...
result:
ok 1681 numbers
Test #11:
score: 0
Accepted
time: 7ms
memory: 4352kb
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.341667965588 7.615773105864 19.235399881682 17.262680444705 14.142135623731 18.027764372991 10.198046879677 11.704699910720 6.000000000000 16.031219541881 14.035676835267 3.000000000000 7.280125289047 20.099751242242 14.142139587489 13.000000000000 16.278804854418 4.472135955000 8.944271909999 5....
result:
ok 1681 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 4352kb
input:
3 2 1 1 2 4 0 1 0 -1 -7 0
output:
7.071067811865
result:
ok found '7.0710678', expected '7.0710678', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
3 2 1 1 2 4 0 1 -1 -999001 -7 0
output:
7.071066820926
result:
ok found '7.0710668', expected '7.0710668', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4352kb
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.000000000000 0.000000000000 1.000000000000 0.000000000000 1.000000000000 2.000000000000 1.000000000000 0.000000000000 1.000000000000 2.000000000000 3.000000000000 4.000000000000 5.000000000000 6.000000000000 7.000000000000 8.000000000000 9.000000000000 10.000000000000 1.414213562373 2.236067977500...
result:
ok 36 numbers
Test #15:
score: 0
Accepted
time: 1ms
memory: 4224kb
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.318273189507 3.147379239224 3.043003664557 5.601139657638 6.294758478447 6.553438496857 6.086007329113 7.480164533118
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.998865701869 14.525423018761 21.073102117794 31.843189113241 153.586804184439 49.991391054940 60.506629716442 71.304136747255 185.430389126834 97.063707637896 110.473497929995 123.630698796005 135.359725664140 243.157701447671 162.608797453795 176.642804156470 189.584451543515 204.318441802607 30...