QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194975 | #3854. Radar | realcomplex0# | WA | 0ms | 3876kb | C++14 | 2.7kb | 2023-09-30 23:58:40 | 2023-09-30 23:58:41 |
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);
struct angle{
ld x;
ld y;
bool operator< (const angle &aa) const {
return x * aa.y - y * aa.x > 0;
}
};
vector<ld> radii;
set<angle> 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("in_a.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({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;
auto it = ang.upper_bound({x,y});
auto pv = it;
res = (ld)1e18;
for(int iter = 0; iter < 2; iter ++ ){
cur = atan2(it->x, it->y);
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 < 2; iter ++ ){
if(pv == ang.begin()){
pv = ang.end();
}
pv -- ;
cur = atan2(pv->x, pv->y);
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: 0ms
memory: 3876kb
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: -100
Wrong Answer
time: 0ms
memory: 3872kb
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 4.95000256 0.07106781 0.07106781 0.07106781 0.07106781 2.00000000 2.00000000 2.0000...
result:
wrong answer 20th numbers differ - expected: '2.0000000', found: '4.9500026', error = '1.4750013'