QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#549639 | #7670. Messenger | karuna | WA | 0ms | 3876kb | C++20 | 6.1kb | 2024-09-06 19:14:41 | 2024-09-06 19:14:41 |
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) {
double ss = e[q], ee = e[q + 1];
point P = x[p] + (t - d[p]) * vecx;
for (int it = 0; it < 30; it++) {
double mid = (ss + ee) / 2;
point Q = y[q] + (mid - e[q]) * vecy;
if (dst(P, Q) > mid - t + eps) ss = mid;
else ee = mid;
}
return ss;
};
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 < 30; 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 < 30; 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 < 30; 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';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
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: 3876kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
5.0000019514
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: -100
Wrong Answer
time: 0ms
memory: 3832kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.0782543704
result:
wrong answer read 0.078254370400 but expected 0.000000000000