QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549656#7670. MessengerkarunaTL 1ms3916kbC++206.2kb2024-09-06 19:20:082024-09-06 19:20:09

Judging History

你现在查看的是最新测评结果

  • [2024-09-06 19:20:09]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3916kb
  • [2024-09-06 19:20:08]
  • 提交

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;
			int iter = 60;
			for (int it = 0; it < iter; 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
			int iter = 60;
			for (int it = 0; it < iter; 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
			int iter = 60;
			for (int it = 0; it < iter; 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: 1ms
memory: 3844kb

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: 3720kb

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: 3852kb

input:

2
0 30000
0 0
2
0 0
30000 0

output:

impossible

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

2
0 30000
0 0
2
30000 0
0 0

output:

0.0000004080

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

2
30000 0
0 0
2
30000 30000
0 30000

output:

impossible

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3916kb

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 ...

output:


result: