QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346701 | #3854. Radar | Kirill22# | WA | 5ms | 3940kb | C++23 | 2.2kb | 2024-03-08 21:23:47 | 2024-03-08 21:23:47 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ld long double
#define point pair<ld, ld>
#define x first
#define y second
point operator-(point a, point b) {
return {a.x - b.x, a.y - b.y};
}
point operator*(point a, ld d) {
return {a.x * d, a.y * d};
}
ld sq(point a) {
return sqrtl(a.x * a.x + a.y * a.y);
}
ld sin(point a, point b) {
return a.x * b.y - a.y * b.x;
}
int id(point a) {
if (a.y > 0 || (a.y == 0 && a.x >= 0)) {
return 0;
}
return 1;
}
bool cmp(point a, point b) {
if (id(a) != id(b)) return id(a) < id(b);
if (sin(a, b) == 0) return a < b;
return sin(a, b) > 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int R, n, q;
cin >> R >> n >> q;
vector<ld> r(R);
for (auto& x : r) {
cin >> x;
}
std::sort(r.begin(), r.end());
vector<point> a(n);
for (auto& x : a) {
cin >> x.x >> x.y;
x = x * (1 / (ld) sq(x));
}
std::sort(a.begin(), a.end(), cmp);
while (q--) {
point t;
cin >> t.x >> t.y;
ld ans = 1e18;
int it = std::lower_bound(a.begin(), a.end(), t, cmp) - a.begin();
for (int x = -10; x <= 10; x++) {
int i = (it + x) % n;
if (i < 0) i += n;
// if (i == n - 1) {
// cout << a[i].x << " " << a[i].y << endl;
// cout << a[i].x * 4 << " " << a[i].y * 4 << endl;
// }
// ans = min(ans, sq(t - a[i] * r[j]));
ld d = abs(a[i].x * t.x + a[i].y * t.y);
int it2 = std::lower_bound(r.begin(), r.end(), d) - r.begin();
// cout << d << " " << it << endl;
// for (int i = 0; i < R; i++) upd(i);
if (it2 < r.size()) {
ans = min(ans, sq(t - a[i] * r[it2]));
}
if (it2 + 1 < r.size()) {
ans = min(ans, sq(t - a[i] * r[it2 + 1]));
}
if (it2) {
ans = min(ans, sq(t - a[i] * r[it2 - 1]));
}
}
cout << fixed << setprecision(15) << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
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.605291072916640 0.977772290465605 1.551845105401790 1.414213562373095
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3756kb
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.874985099257575 15.874985099257575 15.874985099257575 15.874985099257575 15.874985099257575 15.874985099257575 15.874985099257575 15.874985099257575 4.929656701045723 4.929656701045723 4.929656701045723 4.929656701045723 4.929656701045723 4.929656701045723 4.929656701045723 4.929656701045723 2.00...
result:
ok 32 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3940kb
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.055385138137417 4.123105625617661 3.605551275463989 11.045361017187261 15.297058540778354 1.414213562373095 8.246211251235321 7.000000000000000 8.944271909999159 3.000000000000000 12.165525060596439 5.000000000000000 5.099019513592785 11.180339887498948 1.414213562373095 2.000000000000000 2.000000...
result:
ok 1681 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3764kb
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.777372119303551 4.631593682590214 6.895656100977256 12.291422905366941 6.555964003580544 4.270304206047021 4.392536000447645 6.367825885745278 6.555964003580544 2.990316379370501 10.187520359495127 2.833626166508712 2.977064831365349 4.696779860161953 4.352239888693120 11.328455809796768 3.384030...
result:
ok 1681 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
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.000000000000000 4.000000000000000 4.000000000000000 4.000000000000000 5.000000000000000 5.000000000000000 5.000000000000000 5.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 8.062257748298550 8.062257748298550 8.062257748298550 8.062257748298550
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3752kb
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.000000000000000 2.000000000000000 4.000000000000000 8.000000000000000 16.000000000000000 32.000000000000000 64.000000000000000 128.000000000000000 256.000000000000000 512.000000000000000 1024.000000000000000 2048.000000000000000 4096.000000000000000 8192.000000000000000 16384.000000000000000 32768...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 5ms
memory: 3828kb
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.393071595899558 16.453441243476639 14.475640085235758 19.043231368144237 16.182932417451168 19.043231368144237 19.010576536590187 3.305893553660572 11.763187620795244 14.667308360055634 16.295525639797088 7.617705510947693 16.692652903019119 25.870057685088936 16.182932198759698 20.084870431584898...
result:
ok 1681 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3932kb
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.000000000000000 3.000000000000000 2.000000000000000 1.000000000000000 0.000000000000000 1.000000000000000 2.000000000000000 1.000000000000000 0.000000000000000 1.000000000000000 2.000000000000000 3.000000000000000 4.000000000000000 3.000000000000000 2.000000000000000 1.000000000000000 0.0000000000...
result:
ok 108 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 3916kb
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.219544457292887 3.162277660168379 15.033296378372908 6.708203932499369 6.000000000000000 19.104973174542800 12.000000000000000 1.000000000000000 5.656854249492380 4.123105625617661 1.414213562373095 5.099019513592785 12.369316876852982 19.235384061671345 6.000000000000000 9.486832980505138 6.32455...
result:
ok 1681 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3832kb
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.414213562373095 18.439088914585775 4.472135954999579 12.041594578792295 14.317821063276353 10.440306508910550 19.026297590440448 15.033296378372908 3.605551275463989 8.544003745317531 18.027756377319946 17.464249196572981 20.000000000000000 5.000000000000000 13.341664064126334 10.049875621120890 1...
result:
ok 1681 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 3832kb
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.341667965588257 7.615773105863908 19.235399881681894 17.262680444705100 14.142135623730950 18.027764372990675 10.198046879676520 11.704699910719625 6.000000000000000 16.031219541881397 14.035676835267186 3.000000000000000 7.280125289047176 20.099751242241781 14.142139587489014 13.000000000000000 ...
result:
ok 1681 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 2 1 1 2 4 0 1 0 -1 -7 0
output:
7.071067811865475
result:
ok found '7.0710678', expected '7.0710678', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 2 1 1 2 4 0 1 -1 -999001 -7 0
output:
7.071066820925964
result:
ok found '7.0710668', expected '7.0710668', error '0.0000000'
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3820kb
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.000000000000000 0.000000000000000 1.000000000000000 0.000000000000000 1.000000000000000 2.000000000000000 1.000000000000000 0.000000000000000 1.000000000000000 2.000000000000000 3.000000000000000 5.000000000000000 6.000000000000000 9.000000000000000 10.000000000000000 11.000000000000000 12.0000000...
result:
wrong answer 12th numbers differ - expected: '4.0000000', found: '5.0000000', error = '0.2500000'