QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509494 | #3854. Radar | wisniewskij | WA | 3ms | 3944kb | C++20 | 2.9kb | 2024-08-08 15:21:43 | 2024-08-08 15:21:43 |
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 : loc_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: 3868kb
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: 3ms
memory: 3916kb
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: -100
Wrong Answer
time: 2ms
memory: 3944kb
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:
wrong answer 374th numbers differ - expected: '11.7890061', found: '12.2458698', error = '0.0387534'