QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187406 | #3854. Radar | ballance# | WA | 125ms | 5764kb | C++17 | 1.8kb | 2023-09-24 17:00:00 | 2023-09-24 17:00:00 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld PI = 3.14159265358;
ld angle(ld x, ld y)
{
if (x == 0)
{
if (y > 0)
return PI / 2;
return -PI / 2;
}
if (x > 0)
return atan(ld(y) / x);
else
if (y < 0)return -PI + atan(ld(y) / x);
else
return PI + atan(ld(y) / x);
}
ld len(ld x, ld y)
{
return sqrt(x * x + y * y);
}
const int N = 100010;
int r[N];
ld a[N];
ld len2(ld alpha, ld r, ld x, ld y)
{
ld dx = r * cos(alpha), dy = r * sin(alpha);
return len(dx - x, dy - y);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int rr, ff, tt;
cin >> rr >> ff >> tt;
for (int i = 1; i <= rr; i++)
cin >> r[i];
sort(r + 1, r + rr + 1);
r[0] = -1e8;
r[rr + 1] = 1e8;
for (int i = 1; i <= ff; i++)
{
int x, y; cin >> x >> y;
a[i] = angle(x, y);
//cout << x << ' ' << y << ' ' << a[i] << '\n';
}
sort(a + 1, a + ff + 1);
a[ff + 1] = a[1] + 2 * PI;
a[0] = a[ff] - 2 * PI;
while (tt--)
{
int x, y; cin >> x >> y;
ld leng = len(x, y);
/*int l = lower_bound(r, r + rr + 2, leng) - r;
int s[3];
s[1] = r[l - 1], s[2] = r[l];*/
ld alpha = angle(x, y);
int l = lower_bound(a + 1, a + ff + 2, alpha) - a;
ld p[3];
p[1] = a[l - 1], p[2] = a[l];
ld ans = 1e10;
for (int i = 1; i <= 2; i++)
{
ld beta = p[i];
ld shadowlen = leng * cos(beta - alpha);
int l = lower_bound(r, r + rr + 2, shadowlen) - r;
int s[3];
s[1] = r[l - 1], s[2] = r[l];
for (int j = 1; j <= 2; j++)
ans = min(ans, len2(beta, s[j], x, y));
}
cout << fixed << setprecision(15) << ans << '\n';
}
}
/*
2 1 1
1 2
1 0
-1 2
2 1 1
1 2
0 1
1 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
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.605291072920783 0.977772290465605 1.551845105360774 1.414213562373095
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
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.874985099288110 15.874985099257575 15.874985099227040 15.874985099257575 15.874985099227040 15.874985099288110 4.929656701045723 4.929656701045723 4.929656701055556 4.929656701045723 4.929656701035890 4.929656701045723 4.929656701035890 4.929656701055556 2.00...
result:
ok 32 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3636kb
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.055385138215283 4.123105625655664 3.605551275420531 11.045361017265284 15.297058540701530 1.414213562317696 8.246211251311327 6.999999999921655 8.944271910069233 2.999999999843309 12.165525060519160 5.000000000023504 5.099019513592785 11.180339887344785 1.414213562373095 2.000000000000000 2.000000...
result:
ok 1681 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3816kb
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.895656100896918 12.291422905213700 6.555964003580544 4.270304206124859 4.392536000447645 6.367825885823576 6.555964003648145 2.990316379370501 10.187520359484252 2.833626166479386 2.977064831439783 4.696779860279904 4.352239888845865 11.328455809796768 3.384030...
result:
ok 1681 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3708kb
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 4.999999999979434 4.999999999979434 4.999999999958869 4.999999999958869 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 8.062257748264538 8.062257748264538 8.062257748230527 8.062257748230527
result:
ok 16 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3812kb
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:
0.999999999990207 1.999999999980414 3.999999999960827 7.999999999921655 15.999999999843309 31.999999999686618 63.999999999373237 127.999999998746473 255.999999997492947 511.999999994985893 1023.999999989971786 2047.999999979943572 4095.999999959887144 8191.999999919774288 16383.999999839548576 32767...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 2ms
memory: 3636kb
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.453441243482532 14.475640085235758 19.043231368148964 16.182932417446889 19.043231368144237 19.010576536588730 3.305893553660572 11.763187620795244 14.667308360055634 16.295525639790289 7.617705510947693 16.692652903019119 25.870057685088936 16.182932198759698 20.084870431581451...
result:
ok 1681 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3708kb
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.000000000019586 1.000000000000000 2.000000000000000 1.000000000000000 0.000000000039173 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: 3692kb
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.219544457273767 3.162277660019729 15.033296378353365 6.708203932359221 6.000000000078345 19.104973174503843 12.000000000078345 0.999999999980414 5.656854249436982 4.123105625541654 1.414213562428494 5.099019513554373 12.369316876776975 19.235384061593958 5.999999999921655 9.486832980579463 6.32455...
result:
ok 1681 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3716kb
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.414213562428494 18.439088914624015 4.472135954964542 12.041594578714221 14.317821063314656 10.440306508985591 19.026297590518685 15.033296378451080 3.605551275420531 8.544003745390888 18.027756377359059 17.464249196611112 20.000000000078345 4.999999999952993 13.341664064202673 10.049875621101401 1...
result:
ok 1681 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 3640kb
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.341667965550088 7.615773105935919 19.235399881527120 17.262680444666523 14.142135623808508 18.027764372912450 10.198046879599696 11.704699910645997 5.999999999921655 16.031219541920494 14.035676835189040 3.000000000019586 7.280125288896514 20.099751242261270 14.142139587450235 12.999999999921655 ...
result:
ok 1681 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
3 2 1 1 2 4 0 1 0 -1 -7 0
output:
7.071067811850933
result:
ok found '7.0710678', expected '7.0710678', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
3 2 1 1 2 4 0 1 -1 -999001 -7 0
output:
7.071066820916269
result:
ok found '7.0710668', expected '7.0710668', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3644kb
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.000000000004897 0.000000000009793 1.000000000000000 0.000000000019586 1.000000000000000 2.000000000000000 1.000000000000000 0.000000000039173 1.000000000000000 2.000000000000000 3.000000000000000 4.000000000000000 5.000000000000000 6.000000000000000 7.000000000000000 8.000000000000000 9.0000000000...
result:
ok 36 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3804kb
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.318273189544933 3.147379239204565 3.043003664594787 5.601139657563804 6.294758478409130 6.553438496895029 6.086007329189575 7.480164533193865
result:
ok 8 numbers
Test #16:
score: 0
Accepted
time: 118ms
memory: 5764kb
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...
output:
10.998865701868259 14.525423018693443 21.073102117701886 31.843189113148612 115.924895013577747 49.991391054842361 60.506629716344534 69.958130039488118 134.902308151180620 90.172561431325273 100.220151411570515 110.154852884972286 119.838138057552403 169.259259924752511 139.857713809874450 149.9038...
result:
ok 99999 numbers
Test #17:
score: 0
Accepted
time: 125ms
memory: 5636kb
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...
output:
10.000000000000000 15.295841308968246 21.472081503158730 30.839308519800434 35.006555272523730 50.931458107477317 60.506619828997751 70.363795442201725 80.007038937115761 90.056171321627367 100.000633293051919 110.050508279773909 119.838128085721262 129.885197989281585 134.868076476158608 149.833874...
result:
ok 99999 numbers
Test #18:
score: -100
Wrong Answer
time: 120ms
memory: 5656kb
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...
output:
10.000000000000000 11.793537328942145 15.006851569378945 30.316874089052133 40.113906820859334 50.140933717450126 60.175584315259198 70.363795442201725 80.125534801392465 89.856351459773306 100.000633293051919 109.955169614314125 119.767282240876358 129.812131979221724 139.932670846875566 149.713860...
result:
wrong answer 50191st numbers differ - expected: '0.2258785', found: '0.2258863', error = '0.0000077'