QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549697 | #7670. Messenger | karuna | AC ✓ | 927ms | 8680kb | C++20 | 3.5kb | 2024-09-06 19:42:56 | 2024-09-06 19:42:57 |
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;
typedef long double ld;
const ld eps = 1e-9;
struct point {
ld 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}; }
ld operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
ld operator/(point a, point b) { return a.x * b.y - a.y * b.x; }
point operator*(ld k, point a) { return {k * a.x, k * a.y}; }
ld 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]; ld 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]; ld 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;
ld prv = 0;
ld 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 = [&](ld 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]) {
ld ss = prv, ee = d[p + 1];
// ternary search
for (int it = 0; it < 100; it++) {
ld mid1 = (2 * ss + ee) / 3;
ld mid2 = (ss + 2 * ee) / 3;
ld k1 = get(mid1);
ld 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;
ld d1 = dst(P1, Q1);
ld d2 = dst(P2, Q2);
ans = min(ans, min(d1, d2));
if (d1 > d2) {
ss = mid1;
}
else {
ee = mid2;
}
}
prv = d[p + 1];
++p;
}
else {
ld cur;
{
ld ss = d[p], ee = d[p + 1];
for (int it = 0; it < 60; it++) {
ld 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;
}
ld ss = prv, ee = cur;
// ternary search
for (int it = 0; it < 100; it++) {
ld mid1 = (2 * ss + ee) / 3;
ld mid2 = (ss + 2 * ee) / 3;
ld k1 = get(mid1);
ld 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;
ld d1 = dst(P1, Q1);
ld 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: 1ms
memory: 3984kb
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: 3988kb
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: 3804kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0000020019
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
30000.0000000000
result:
ok correct
Test #7:
score: 0
Accepted
time: 547ms
memory: 8620kb
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.3137084990
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.0000047322
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3928kb
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: 3868kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.0000000071
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
1.0000000000
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3872kb
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: 3728kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.0000000157
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3884kb
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: 3816kb
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: 3888kb
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: 3820kb
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: 487ms
memory: 8680kb
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.1356237310
result:
ok correct
Test #24:
score: 0
Accepted
time: 927ms
memory: 8512kb
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: 3940kb
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: 3976kb
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: 1ms
memory: 3992kb
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: 2ms
memory: 3956kb
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.0104863369
result:
ok correct
Test #30:
score: 0
Accepted
time: 3ms
memory: 3888kb
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.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 4008kb
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.2276317226
result:
ok correct
Test #32:
score: 0
Accepted
time: 10ms
memory: 3920kb
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.2479691706
result:
ok correct
Test #33:
score: 0
Accepted
time: 336ms
memory: 5604kb
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.0000000334
result:
ok correct
Test #34:
score: 0
Accepted
time: 31ms
memory: 4280kb
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.0144415775
result:
ok correct
Test #35:
score: 0
Accepted
time: 927ms
memory: 8580kb
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.0000754374
result:
ok correct
Test #36:
score: 0
Accepted
time: 923ms
memory: 8556kb
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.0000002269
result:
ok correct
Test #37:
score: 0
Accepted
time: 11ms
memory: 6288kb
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: 11ms
memory: 6168kb
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: 9ms
memory: 5604kb
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: 19ms
memory: 5860kb
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: 1ms
memory: 3980kb
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: 3920kb
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: 2ms
memory: 3908kb
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.8897882802
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 3952kb
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.5386713685
result:
ok correct
Test #45:
score: 0
Accepted
time: 886ms
memory: 8636kb
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:
42332.4154625882
result:
ok correct
Test #46:
score: 0
Accepted
time: 882ms
memory: 8660kb
input:
50000 31 13 2 25 10 20 1 31 9 33 9 28 0 32 30 20 18 15 30 34 10 20 6 1 34 14 26 21 19 18 20 27 11 34 12 18 29 32 8 26 34 10 12 16 15 35 33 30 23 19 26 7 32 12 6 10 27 33 14 11 23 8 6 7 15 10 1 32 16 17 31 26 8 8 11 23 10 34 6 15 7 29 2 16 6 35 17 14 5 8 28 2 6 12 32 7 30 27 6 23 15 27 20 30 17 2 31 ...
output:
42333.5614531335
result:
ok correct