QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509508 | #3854. Radar | wisniewskij | TL | 2ms | 4012kb | C++20 | 3.0kb | 2024-08-08 15:31:43 | 2024-08-08 15:31:44 |
Judging History
answer
#include <bits/stdc++.h>
#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<long double, long double> point;
long double dist(point a, point b){
long double y = b.nd - a.nd, x = b.st - a.st;
return sqrt(y*y + x*x);
}
point pos(point angle, long double rad){
long double dis = dist(angle, {0, 0});
if(dis == 0) return angle;
return {rad / dis * angle.st, rad / dis * angle.nd};
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int R, F, N; cin>>R>>F>>N;
vector<long double> radii(R); for(auto &x: radii) cin>>x;
vector<point> angles(F), points(N);
for(auto &[x, y]: angles) cin>>x>>y;
for(auto &[x, y]: points) cin>>x>>y;
sort(all(radii));
sort(all(angles), [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
for(auto pt : points) {
vector<vector<point>::iterator>loc_angles;
{
auto right_angle = upper_bound(all(angles), pt, [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
if(right_angle == angles.end()) right_angle = angles.begin();
loc_angles.push_back(right_angle);
if(points.size() > 1) {
auto left_angle = right_angle;
if(left_angle == angles.begin()) left_angle = angles.end();
left_angle--;
loc_angles.push_back(left_angle);
if(points.size() > 2) {
if(left_angle == angles.begin()) left_angle = angles.end();
left_angle--;
loc_angles.push_back(left_angle);
}
}
}
// vector<long double> loc_radii;
// {
// auto upper_radius = upper_bound(all(radii), sqrt(pt.st*pt.st + pt.nd*pt.nd));
// if(upper_radius == radii.end()) {
// upper_radius--;
// loc_radii.push_back(*upper_radius);
// } else {
// loc_radii.push_back(*upper_radius);
// if(upper_radius != radii.begin()) {
// upper_radius--;
// loc_radii.push_back(*(upper_radius));
// if(upper_radius != radii.begin()) {
// upper_radius--;
// loc_radii.push_back(*(upper_radius));
// }
// }
// }
// }
vector<long double> zzz;
for(auto l_angle : loc_angles) {
for(auto l_radius : radii) {
zzz.push_back(dist(pos(*l_angle, l_radius), pt));
}
}
sort(all(zzz));
cout<<setprecision(20)<<zzz[0]<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
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.60529107291663996433 0.9777722904656049825 1.5518451054017895745 1.4142135623730950488
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3940kb
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.874985099257575043 15.874985099257575043 15.874985099257575043 15.874985099257575043 15.874985099257575043 15.874985099257575043 15.874985099257575043 15.874985099257575043 4.9296567010457233234 4.9296567010457233234 4.9296567010457233234 4.9296567010457233234 4.9296567010457233234 4.929656701045...
result:
ok 32 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3912kb
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.0553851381374166262 4.1231056256176605497 3.6055512754639892931 11.045361017187260775 15.297058540778354491 1.4142135623730950488 8.2462112512353210993 7 8.9442719099991587857 3 12.165525060596439378 5 5.0990195135927848299 11.180339887498948482 1.4142135623730950488 2 2 3 3.162277660168379332 8.2...
result:
ok 1681 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3916kb
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.777372119303551408 4.6315936825902144745 6.8956561009772562314 12.291422905366941493 6.5559640035805438938 4.2703042060470206408 4.3925360004476450668 6.3678258857452781101 6.5559640035805438938 2.9903163793705008662 10.187520359495127463 2.8336261665087121042 2.9770648313653493725 4.696779860161...
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 4 4 4 5 5 5 5 1 1 1 1 8.0622577482985496528 8.0622577482985496528 8.0622577482985496528 8.0622577482985496528
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3876kb
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 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1047.0004775548099052 2095.0002386634708926 4190.0001193317405441 8380.0000596658709089 16760.000029832935533 33520.000014916467777 67041.000007458122639 134083.00000372903351 268167.00000186450981 536334.0000009...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 4012kb
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.3930715958995580628 16.453441243476639316 14.475640085235757517 19.043231368144236875 16.182932417451168141 19.043231368144236875 19.010576536590186713 3.3058935536605719265 11.763187620795244258 14.667308360055634381 16.295525639797087843 7.6177055109476934556 16.692652903019119082 25.87005768508...
result:
ok 1681 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3888kb
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 3 2 1 0 1 2 1 0 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 0 1 2 1 0 1 2 3 4 3 2 1 0 1 2 3 4 4.1231056256176605497 4.4721359549995793928 5 5.6568542494923801951 6.4031242374328486864 7.2111025509279785863 8.0622577482985496528 8.9442719099991587857 9.8488578017961047216 10.770329614269008063 11.704699910719625...
result:
ok 108 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3924kb
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.21954445729288731 3.162277660168379332 15.033296378372908271 6.708203932499369089 6 19.104973174542800179 12 1 5.6568542494923801951 4.1231056256176605497 1.4142135623730950488 5.0990195135927848299 12.369316876852981649 19.235384061671344753 6 9.4868329805051379959 6.3245553203367586639 4.1231056...
result:
ok 1681 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 4004kb
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.4142135623730950488 18.43908891458577462 4.4721359549995793928 12.04159457879229548 14.317821063276353155 10.44030650891055018 19.026297590440448064 15.033296378372908271 3.6055512754639892931 8.5440037453175311675 18.027756377319946466 17.464249196572980647 20 5 13.341664064126333713 10.049875621...
result:
ok 1681 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 4012kb
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.34166796558825713 7.6157731058639082855 19.235399881681893625 17.262680444705100078 14.142135623730950488 18.02776437299067473 10.198046879676519698 11.704699910719625109 6 16.031219541881397365 14.035676835267185921 3 7.2801252890471757242 20.09975124224178054 14.142139587489013886 13 16.2788048...
result:
ok 1681 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
3 2 1 1 2 4 0 1 0 -1 -7 0
output:
7.0710678118654752438
result:
ok found '7.0710678', expected '7.0710678', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 2 1 1 2 4 0 1 -1 -999001 -7 0
output:
7.0710668209259636453
result:
ok found '7.0710668', expected '7.0710668', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3804kb
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 0 1 0 1 2 1 0 1 2 3 4 5 6 7 8 9 10 1.4142135623730950488 2.2360679774997896964 3.162277660168379332 4.1231056256176605497 5.0990195135927848299 6.0827625302982196889 7.0710678118654752438 8.0622577482985496528 9.0553851381374166262 1.4142135623730950488 2.2360679774997896964 3.162277660168379332 4...
result:
ok 36 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3880kb
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.3182731895074407177 3.147379239223550823 3.043003664556540048 5.6011396576375128377 6.294758478447101646 6.5534384968572901029 6.0860073291130800961 7.4801645331180126558
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...