QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549564 | #7670. Messenger | karuna | TL | 1ms | 3940kb | C++20 | 4.2kb | 2024-09-06 17:39:09 | 2024-09-06 17:39:11 |
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; }
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++) 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++) 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");
}
auto get_x = [&](double t, int p) {
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]);
};
auto get_y = [&](double t, int p) {
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) {
double ss = 0, ee = e[m - 1] + 1e-3;
point P = get_x(t, p);
// cout << "P = (" << P.x << ", " << P.y << ")\n";
for (int it = 0; it < 70; it++) {
double mid = (ss + ee) / 2;
point Q = get_y(mid, q);
// cout << mid << " -> (" << Q.x << ' ' << Q.y << "), dst = " << dst(P, Q) << ", RHS = " << mid - t + eps << '\n';
if (dst(P, Q) > mid - t + eps) ss = mid;
else ee = mid;
}
return ss > e[m - 1] + eps ? -1 : ss;
};
auto go_y = [&](double t, int p, int q) {
// cout << "go_y " << t << ' ' << p << ' ' << q << endl;
double ss = -1e-3, ee = d[n - 1];
point Q = get_y(t, q);
// cout << "Q = (" << Q.x << ", " << Q.y << ")\n";
for (int it = 0; it < 70; it++) {
double mid = (ss + ee) / 2;
point P = get_x(mid, p);
// cout << mid << " -> (" << P.x << ' ' << P.y << "), dst = " << dst(P, Q) << ", RHS = " << t - mid + eps << '\n';
if (dst(P, Q) > t - mid + eps) ee = mid;
else ss = mid;
}
return ss < -eps ? -1 : ss;
};
auto ternary = [&](double ss, double ee, int p, int q) {
// cout << "ternary " << ss << ' ' << ee << ' ' << p << ' ' << q << endl;
double ret = 1e9;
for (int it = 0; it < 70; 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.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: 3940kb
input:
2 0 0 0 10 2 4 10 4 0
output:
4.0000000000
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
4.9999999960
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0000000005
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
30000.0000000000
result:
ok correct
Test #7:
score: -100
Time Limit Exceeded
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 ...