QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549564#7670. MessengerkarunaTL 1ms3940kbC++204.2kb2024-09-06 17:39:092024-09-06 17:39:11

Judging History

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

  • [2024-09-06 17:39:11]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3940kb
  • [2024-09-06 17:39:09]
  • 提交

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

output:


result: