QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549671 | #7670. Messenger | karuna | WA | 299ms | 6288kb | C++20 | 6.0kb | 2024-09-06 19:33:28 | 2024-09-06 19:33:29 |
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 - e[p]) * vecx - y[q] + e[q] * vecy;
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';
// int callx = 0;
// auto get_x = [&](double t, int p) {
// ++callx;
// if (p == -1) {
// p = upper_bound(d, d + n, t) - d;
// if (t < eps) p = 1;
// if (t > d[m - 1] - eps) p = n - 1;
// }
// if (p == 0) p = 1;
// return x[p - 1] + (t - d[p - 1]) * unit(x[p] - x[p - 1]);
// };
// int cally = 0;
// auto get_y = [&](double t, int p) {
// ++cally;
// if (p == -1) {
// p = upper_bound(e, e + m, t) - e;
// if (t < eps) p = 1;
// if (t > e[m - 1] - eps) p = m - 1;
// }
// if (p == 0) p = 1;
// return y[p - 1] + (t - e[p - 1]) * unit(y[p] - y[p - 1]);
// };
// auto go_x = [&](double t, int p, int q) {
// return ss > e[m - 1] + eps ? -1 : ss;
// };
// auto go_y = [&](double t, int p, int q) {
// };
// int callt = 0;
// auto ternary = [&](double ss, double ee, int p, int q) {
// ++callt;
// return (double)1e9;
// // cout << "ternary " << ss << ' ' << ee << ' ' << p << ' ' << q << endl;
// double ret = 1e9;
// for (int it = 0; it < 60; it++) {
// double mid1 = (2 * ss + ee) / 3;
// double mid2 = (ss + 2 * ee) / 3;
// point P1 = get_x(mid1, p), Q1 = get_y(go_x(mid1, p, q), q);
// point P2 = get_x(mid2, p), Q2 = get_y(go_x(mid2, p, q), q);
// ret = min(ret, dst(P1, Q1));
// ret = min(ret, dst(P2, Q2));
// if (dst(P1, Q1) > dst(P2, Q2)) ss = mid1;
// else ee = mid2;
// }
// return ret;
// };
// // {
// // point p = get_x(3, -1);
// // cout << p.x << ' ' << p.y << '\n';
// // point q = get_y(go_x(0, -1, -1), -1);
// // cout << q.x << ' ' << q.y << '\n';
// // }
// // return 0;
// // cout << go_x(0, -1, -1) << endl;
// // return 0;
// // cout << go_y(e[1], -1, 1) << endl;
// // return 0;
// double ans = 1e18;
// double prv = d[0];
// for (int p = 0, q = 0; p < n - 1; p++) {
// while (q < m && go_y(e[q], -1, q) == -1) ++q;
// double cur = d[p + 1];
// bool flag = false;
// if (cur == -1) flag = true, cur = 1e9;
// while (q < m) {
// double t = go_y(e[q], -1, q);
// if (t >= cur + eps) break;
// while (t < cur + eps) {
// ans = min(ans, ternary(prv, t, p + 1, q));
// prv = t;
// if (!(++q < m - 1)) break;
// t = go_y(e[q], -1, q);
// }
// }
// if (flag) break;
// ans = min(ans, ternary(prv, cur, p + 1, q));
// prv = cur;
// }
// cout << callt << ' ' << callx << ' ' << cally << endl;
// 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: 3852kb
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: 3908kb
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: 3724kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
30000.0000000000
result:
ok correct
Test #7:
score: 0
Accepted
time: 181ms
memory: 6288kb
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: 3852kb
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: 3776kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3848kb
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: 3864kb
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: 3908kb
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: 3796kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3940kb
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: 3724kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3864kb
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: 3788kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
0.0002419855
result:
ok correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 3844kb
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: 3956kb
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: 169ms
memory: 6204kb
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: 299ms
memory: 6252kb
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: 3956kb
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: -100
Wrong Answer
time: 0ms
memory: 3868kb
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.7083292537
result:
wrong answer read 1.708329253700 but expected 1.973569097421