QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509529 | #3854. Radar | wisniewskij | WA | 0ms | 3916kb | C++20 | 2.7kb | 2024-08-08 15:41:51 | 2024-08-08 15:41:51 |
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};
}
long double dot_prod(point a, point b){
return a.st * b.st + a.nd * b.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);
}
}
vector<long double> loc_radii;
for(auto l_angle : loc_angles){
auto upper_radius = upper_bound(all(radii), dot_prod({(*l_angle).st, (*l_angle).nd}, pt));
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));
}
}
}
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: 0
Wrong Answer
time: 0ms
memory: 3916kb
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:
5.5930600292088784318 0.9777722904656049825 1.5518451054017895745 1.4142135623730950488
result:
wrong answer 1st numbers differ - expected: '0.6052911', found: '5.5930600', error = '4.9877690'