QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549693 | #7670. Messenger | karuna | WA | 376ms | 6228kb | C++20 | 3.6kb | 2024-09-06 19:41:47 | 2024-09-06 19:41:47 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
struct point {
double x, y;
};
point operator+(point a, point b) { return {a.x + b.x, a.y + b.y}; }
point operator-(point a, point b) { return {a.x - b.x, a.y - b.y}; }
double operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
double operator/(point a, point b) { return a.x * b.y - a.y * b.x; }
point operator*(double k, point a) { return {k * a.x, k * a.y}; }
double dst(point a, point b) { return sqrt((a - b) * (a - b)); }
point unit(point a) { return 1 / sqrt(a * a) * a; }
mt19937 rnd(1557);
int rng(int l, int r) {
return uniform_int_distribution<int>(l, r)(rnd);
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
int n;
cin >> n;
point x[n]; double d[n]{};
// for (int i = 0; i < n; i++) {
// x[i].x = rng(-30000, 30000);
// x[i].y = rng(-30000, 30000);
// }
for (int i = 0; i < n; i++) cin >> x[i].x >> x[i].y;
for (int i = 1; i < n; i++) d[i] = d[i - 1] + dst(x[i], x[i - 1]);
int m;
cin >> m;
point y[m]; double e[m]{};
// for (int i = 0; i < m; i++) {
// y[i].x = rng(-30000, 30000);
// y[i].y = rng(-30000, 30000);
// }
for (int i = 0; i < m; i++) cin >> y[i].x >> y[i].y;
for (int i = 1; i < m; i++) e[i] = e[i - 1] + dst(y[i], y[i - 1]);
if (dst(x[0], y[m - 1]) > e[m - 1] + eps) {
return !(cout << "impossible\n");
}
int p = 0, q = 0;
while (q < m - 1 && dst(x[0], y[q + 1]) > e[q + 1]) ++q;
double prv = 0;
double ans = 1e9;
while (p != n - 1 && q != m - 1) {
point vecx = unit(x[p + 1] - x[p]);
point vecy = unit(y[q + 1] - y[q]);
auto get = [&](double t) {
point sec = x[p] + (t - d[p]) * vecx - y[q] + e[q] * vecy;
if (abs(sec * vecy - t) < eps) return e[q];
else return (t * t - sec * sec) / (2 * (t - sec * vecy));
};
if (d[p + 1] + dst(x[p + 1], y[q + 1]) < e[q + 1]) {
double ss = prv, ee = d[p + 1];
// ternary search
for (int it = 0; it < 100; it++) {
double mid1 = (2 * ss + ee) / 3;
double mid2 = (ss + 2 * ee) / 3;
double k1 = get(mid1);
double k2 = get(mid2);
point P1 = x[p] + (mid1 - d[p]) * vecx;
point P2 = x[p] + (mid2 - d[p]) * vecx;
point Q1 = y[q] + (k1 - e[q]) * vecy;
point Q2 = y[q] + (k2 - e[q]) * vecy;
double d1 = dst(P1, Q1);
double d2 = dst(P2, Q2);
ans = min(ans, min(d1, d2));
if (d1 > d2) {
ss = mid1;
}
else {
ee = mid2;
}
}
prv = d[p + 1];
++p;
}
else {
double cur;
{
double ss = d[p], ee = d[p + 1];
for (int it = 0; it < 60; it++) {
double mid = (ss + ee) / 2;
point P = x[p] + (mid - d[p]) * vecx;
if (dst(P, y[q + 1]) > e[q + 1] - mid + eps) ee = mid;
else ss = mid;
}
cur = ss;
}
double ss = prv, ee = cur;
// ternary search
for (int it = 0; it < 100; it++) {
double mid1 = (2 * ss + ee) / 3;
double mid2 = (ss + 2 * ee) / 3;
double k1 = get(mid1);
double k2 = get(mid2);
point P1 = x[p] + (mid1 - d[p]) * vecx;
point P2 = x[p] + (mid2 - d[p]) * vecx;
point Q1 = y[q] + (k1 - e[q]) * vecy;
point Q2 = y[q] + (k2 - e[q]) * vecy;
double d1 = dst(P1, Q1);
double d2 = dst(P2, Q2);
ans = min(ans, min(d1, d2));
if (d1 > d2) {
ss = mid1;
}
else {
ee = mid2;
}
}
prv = cur;
++q;
}
}
cout.precision(10);
cout << fixed << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
2 0 0 0 10 2 4 10 4 0
output:
4.0000000000
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
5.0000000000
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0000000011
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
30000.0000000000
result:
ok correct
Test #7:
score: 0
Accepted
time: 222ms
memory: 6220kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
3.3137084953
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.0002599432
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.5000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.0000056062
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.9999999994
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.0000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.0000411623
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
0.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 0 0 0 1 3 30000 12426 30000 0 30000 30000
output:
impossible
result:
ok correct
Test #21:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
2 0 0 0 1 3 30000 12427 30000 0 30000 30000
output:
42424.9750140822
result:
ok correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
4 0 30000 0 0 1 0 1 30000 4 30000 30000 30000 0 29999 0 29999 30000
output:
29999.0000000000
result:
ok correct
Test #23:
score: 0
Accepted
time: 205ms
memory: 6228kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
24142.1356237309
result:
ok correct
Test #24:
score: 0
Accepted
time: 344ms
memory: 6176kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
0.0000000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2 1 10 1 11 5 3 8 2 9 10 2 10 3 8 8
output:
1.4142135623
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 5 0 0 6 3 6 9 0 2 6 8 6 5 2 5 2 2 9 4 5 0 7 0 8 10
output:
1.9735690974
result:
ok correct
Test #27:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
8 4487 25213 15925 2555 11834 19731 24882 25400 29873 18185 20332 1130 20912 4660 2260 17776 7 1181 9778 6861 17903 1110 10850 8648 15950 13243 28850 23075 19352 14768 3464
output:
1452.5639082305
result:
ok correct
Test #28:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
8 5171 18241 3918 24817 6039 21929 19392 10844 5465 21271 18464 27403 5672 17224 17352 23648 8 13743 27832 6508 18183 93 25279 429 836 959 12741 1631 9065 17093 3127 6232 13449
output:
2339.7594870148
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
306 7 0 1 4 9 7 8 6 3 7 2 5 9 2 5 8 6 2 4 9 5 10 10 10 10 3 5 1 3 8 9 6 7 4 8 9 6 4 10 6 6 8 6 3 10 1 0 7 8 5 2 4 1 10 10 10 4 10 10 3 1 10 7 5 1 2 10 8 1 2 3 7 6 1 6 8 5 3 2 8 7 2 0 6 2 5 7 3 0 9 2 9 7 9 8 7 7 1 1 5 7 8 9 3 9 9 0 2 6 7 7 5 5 9 8 4 7 7 8 6 8 0 0 3 0 10 3 6 6 3 1 7 8 5 3 9 7 9 2 7 3 ...
output:
0.0104863363
result:
ok correct
Test #30:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
283 10 2 8 8 2 9 5 3 6 7 6 2 3 3 10 9 10 4 9 7 3 3 9 6 3 10 3 0 6 10 1 7 8 3 0 5 3 8 10 0 9 4 7 3 3 6 3 2 10 5 6 2 3 6 8 3 10 8 2 6 3 4 2 10 2 8 7 10 0 5 5 0 6 6 2 6 8 9 10 3 6 3 3 9 8 10 0 7 0 10 0 8 1 8 7 1 0 1 7 10 0 1 1 9 8 3 5 10 9 6 7 5 9 8 5 8 8 6 3 5 9 1 9 8 6 1 6 0 0 0 8 1 1 10 2 0 5 0 3 1 ...
output:
0.0000001012
result:
ok correct
Test #31:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
99 246 227 1374 887 973 515 505 835 445 502 1524 361 589 217 728 637 988 74 1312 1493 192 485 150 951 903 1575 1358 1114 1564 829 262 1465 922 1078 679 912 561 947 1321 1165 948 1333 684 1456 243 1470 654 1373 894 897 149 1089 424 1162 213 293 845 555 508 441 999 1549 406 1020 16 1437 1335 112 174 1...
output:
18.2276317216
result:
ok correct
Test #32:
score: 0
Accepted
time: 4ms
memory: 3960kb
input:
625 189 776 733 112 1550 794 1148 1341 1236 403 944 153 1152 459 1271 831 203 358 912 1530 1196 1401 1014 758 378 736 130 182 555 20 1425 200 587 755 606 666 1423 1451 624 423 110 1403 26 424 1437 956 796 961 602 1586 331 373 850 800 1559 1508 536 1494 3 598 906 551 1162 1231 1348 106 592 1255 694 1...
output:
4.2479691535
result:
ok correct
Test #33:
score: 0
Accepted
time: 137ms
memory: 4840kb
input:
18051 32 15 3 3 11 2 2 30 32 14 15 25 34 16 10 12 13 31 14 16 15 35 16 24 18 35 24 4 11 22 21 7 24 12 6 32 25 24 23 2 21 2 3 15 13 9 32 6 26 25 21 30 20 23 22 5 16 11 26 15 15 27 25 32 31 28 5 19 15 20 1 25 3 24 30 5 29 11 19 11 26 9 9 29 7 1 15 3 35 32 18 4 13 25 23 25 32 11 10 19 25 0 28 6 5 35 13...
output:
0.0000034641
result:
ok correct
Test #34:
score: 0
Accepted
time: 13ms
memory: 4068kb
input:
1587 1 16 34 21 28 4 16 22 35 8 1 15 20 18 10 15 23 16 1 23 16 14 15 22 3 34 4 35 34 22 32 16 19 20 7 10 13 20 16 8 11 26 24 35 25 26 19 14 21 4 10 11 3 30 15 11 21 12 11 0 25 17 1 0 33 31 2 26 14 21 19 1 0 32 19 19 3 5 30 29 5 18 21 29 28 8 34 2 25 22 14 5 32 7 1 21 13 23 8 35 31 26 9 2 2 24 25 23 ...
output:
0.0144411752
result:
ok correct
Test #35:
score: 0
Accepted
time: 372ms
memory: 6032kb
input:
50000 13 5 18 3 8 23 18 33 27 15 14 27 19 22 32 10 18 32 4 35 19 3 17 12 15 33 7 6 30 19 29 8 23 26 1 16 28 25 19 31 21 9 32 11 8 30 7 16 18 18 11 12 30 9 21 35 4 35 2 5 16 21 24 25 10 7 35 24 21 10 5 30 8 0 22 15 19 0 0 33 29 8 31 6 25 29 22 16 22 24 28 25 22 13 28 22 0 29 27 11 0 12 0 1 24 22 19 1...
output:
0.0000045081
result:
ok correct
Test #36:
score: 0
Accepted
time: 376ms
memory: 6224kb
input:
50000 19 16 34 16 26 17 19 6 30 25 11 13 23 13 26 30 22 5 29 19 0 33 29 15 32 23 7 34 28 27 29 23 34 31 33 14 26 10 23 34 21 35 16 0 0 26 2 2 9 25 2 4 17 9 8 1 4 27 7 5 28 14 24 3 24 18 6 22 35 33 10 0 30 20 8 7 11 12 14 21 8 14 1 14 27 24 5 29 2 14 10 19 20 24 13 31 28 32 18 19 29 14 22 34 34 5 1 2...
output:
0.0001069286
result:
ok correct
Test #37:
score: 0
Accepted
time: 9ms
memory: 5008kb
input:
4 5 5 5 2 4 5 7 6 50000 30 27 31 3 22 30 38 31 39 13 29 33 41 28 21 5 50 26 29 6 42 17 37 12 41 29 35 11 38 30 39 9 45 0 32 7 44 31 40 0 44 30 31 11 31 24 37 4 42 15 23 16 35 28 23 27 25 27 30 35 25 25 44 29 39 12 42 32 44 27 22 22 47 34 22 8 23 14 32 6 39 12 32 25 34 21 29 4 41 35 28 3 40 9 43 19 4...
output:
22.0379614675
result:
ok correct
Test #38:
score: 0
Accepted
time: 9ms
memory: 5004kb
input:
9 4 10 4 1 8 6 7 4 0 5 4 9 10 1 1 2 1 4 50000 48 7 40 0 42 29 22 13 46 19 35 21 40 19 54 15 55 26 36 21 44 16 31 30 20 5 37 31 51 9 45 31 26 15 54 30 51 1 54 2 54 22 31 2 52 19 43 17 26 31 41 20 38 20 39 19 44 34 52 1 33 29 33 11 38 28 30 29 43 20 52 8 36 29 26 20 45 23 39 13 53 5 47 10 52 3 54 7 40...
output:
20.2431066127
result:
ok correct
Test #39:
score: 0
Accepted
time: 7ms
memory: 4776kb
input:
2 4 19317 4 19318 37985 41 27 37 16 47 27 31 15 36 13 24 20 49 25 51 23 49 1 33 16 27 16 53 29 43 17 40 9 20 21 24 3 21 19 44 10 36 20 55 15 30 30 35 32 33 26 26 5 35 29 47 27 50 20 33 31 33 3 34 8 35 20 32 23 34 30 26 17 29 10 36 34 21 25 54 29 40 7 38 17 39 9 46 20 35 30 31 33 20 8 32 30 33 26 37 ...
output:
19289.9111706211
result:
ok correct
Test #40:
score: 0
Accepted
time: 13ms
memory: 4856kb
input:
6 3 25333 0 26159 6 15490 0 3432 4 8641 0 15506 41088 40 9 24 34 30 18 25 25 44 10 55 12 24 14 25 1 21 21 28 16 33 26 42 32 31 34 41 20 50 25 46 4 27 4 23 29 48 8 39 18 54 3 38 14 31 30 55 24 41 2 31 16 45 18 40 32 24 31 39 31 31 2 39 2 26 29 37 22 53 11 29 21 31 31 47 7 35 18 33 4 29 4 28 27 49 14 ...
output:
3406.3776154961
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4 7 18240 5 26771 3 24943 0 6628 7 20 1906 27 15217 20 15532 21 11073 27 334 23 16131 23 18367
output:
3222.0933119308
result:
ok correct
Test #42:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
4 8 15367 9 13231 10 3412 5 16414 10 26 15046 22 22728 24 22149 20 7329 27 26701 22 4714 27 4268 27 13007 28 27715 20 13727
output:
13.8607797505
result:
ok correct
Test #43:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
8 15009 21979 15010 23864 15007 5225 15003 4757 15009 16970 15007 15279 15003 4170 15007 27635 864 14373 15544 14972 14279 14674 14827 14729 14520 15657 15248 14953 14950 14346 14312 14476 14874 14476 15320 15384 15757 15017 15028 14567 14633 15610 14904 14751 15493 14357 14490 15321 14795 14676 151...
output:
17.8897882791
result:
ok correct
Test #44:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
6 15005 29323 15004 1778 15008 23555 15000 19170 15010 25875 15010 15988 154 15757 14866 15689 15407 14776 15688 15444 15769 15627 14793 14834 15211 14211 14961 14905 15228 14634 14324 15317 14937 15402 15641 15290 14306 14925 14641 14936 14261 15472 14801 15124 15800 14660 15632 15311 15017 15074 1...
output:
0.5386713660
result:
ok correct
Test #45:
score: -100
Wrong Answer
time: 358ms
memory: 6180kb
input:
50000 30 20 9 34 25 8 24 4 35 34 6 29 9 15 25 7 4 1 26 21 8 5 31 33 11 28 16 23 29 10 1 30 15 23 14 4 19 22 7 27 11 9 20 12 11 23 30 16 29 24 15 3 5 19 3 2 27 18 25 23 9 2 2 22 18 25 34 35 31 0 35 10 26 28 33 13 28 0 30 33 18 28 0 19 7 25 31 23 26 6 31 33 4 33 5 12 25 15 2 18 22 19 19 5 13 24 13 6 1...
output:
42318.1757789040
result:
wrong answer read 42318.175778903998 but expected 42332.415462588193