QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465445#5104. Guardians of the GallerykarunaWA 2ms4152kbC++206.2kb2024-07-06 21:58:542024-07-06 21:58:55

Judging History

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

  • [2024-07-06 21:58:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4152kb
  • [2024-07-06 21:58:54]
  • 提交

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;

typedef long double ld;

const int SZ = 110;
const ld eps = 1e-9;

struct point {
	int 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}; }
int operator*(point a, point b) { return a.x * b.x + a.y * b.y; }
int operator/(point a, point b) { return a.x * b.y - a.y * b.x; }

int ccw(point p, point q, point r) {
	int s = (q - p) / (r - p);
	return (s > 0) - (s < 0);
}
pii cross(point p, point q, point r, point v) {
	if (v / (q - p) < 0 && v / (r - p) < 0) return {-1, 1};
	if (v / (q - p) > 0 && v / (r - p) > 0) return {-1, 2};
	point u = r - q;
	int a = (q - p) / u, b = v / u;
	if (b == 0 || 1ll * a * b < 0) return {-1, 3};
	if (a < 0) a *= -1, b *= -1;
	return {a, b};
}

struct pointd {
	ld x, y;
	pointd() : x(0), y(0) {}
	pointd(point p) : x(p.x), y(p.y) {}
	pointd(ld x, ld y) : x(x), y(y) {}
};
pointd operator+(pointd a, pointd b) { return {a.x + b.x, a.y + b.y}; }
pointd operator-(pointd a, pointd b) { return {a.x - b.x, a.y - b.y}; }
ld operator*(pointd a, pointd b) { return a.x * b.x + a.y * b.y; }
ld operator/(pointd a, pointd b) { return a.x * b.y - a.y * b.x; }
pointd operator*(ld k, pointd a) { return {k * a.x, k * a.y}; }

int ccw(pointd p, pointd q, pointd r) {
	ld s = (q - p) / (r - p);
	return (s > eps) - (s < -eps);
}
bool point_on_line(pointd p, pointd q, pointd r) {
	ld s = (q - p) * (r - p);
	return ccw(p, q, r) == 0 && -eps <= s && s <= (q - p) * (q - p);
}

pointd hypot(pointd p, pointd q, pointd r, bool &flag) {
	ld s = (q - p) * (r - p);
	if (s < -eps || s > (q - p) * (q - p) + eps) {
		flag = false; return r;
	}
	s /= (q - p) * (q - p);

	// cout << "hypot " << "(" << r.x << ", " << r.y << ") to segment (" << p.x << ", " << p.y << ") and (" << q.x << ", " << q.y << ")\n";
	// cout << "(" << (p + s * (q - p)).x << ", " << (p + s * (q - p)).y << ")\n";
	return p + s * (q - p);
}
bool cross(pointd p, pointd q, pointd r, pointd s) {
	if (ccw(p, q, r) == 0 && ccw(p, q, s) == 0) return false;
	if (point_on_line(p, q, r) || point_on_line(p, q, s) || point_on_line(r, s, p) || point_on_line(r, s, q)) return true;
	return ccw(p, q, r) * ccw(p, q, s) < 0 && ccw(r, s, p) * ccw(r, s, q) < 0;
}
ld intersect(pointd p, pointd u, pointd q, pointd v) {
	return ((q - p) / v) / (u / v);
}

int n; point P[SZ];
vector<pair<ld, int>> G[SZ];
ld ds[SZ];

bool polygon_in(pointd p) {
	bool flag = false;
	for (int i = 0; i < n; i++) {
		pointd q = P[i], r = P[(i + 1) % n];
		if (point_on_line(q, r, p)) return true;
	}
	for (int i = 0; i < n; i++) {
		pointd q = P[i], r = P[(i + 1) % n];
		if (q.y < r.y) swap(q, r);
		if (q.y > p.y + eps && r.y > p.y + eps) continue;
		if (q.y < p.y + eps && r.y < p.y + eps) continue;
		if (ccw(q, r, p) <= 0) {
			flag ^= 1;
		}
	}
	return flag;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	cout.precision(10);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> P[i].x >> P[i].y;
	}
	cin >> P[n].x >> P[n].y;
	cin >> P[n + 1].x >> P[n + 1].y;

	point Q[n];
	for (int i = 0; i < n; i++) Q[i] = P[i];
	auto sgn = [&](point p) {
		return (p.y == 0) ? p.x > 0 : p.y > 0;
	};
	sort(Q, Q + n, [&](point p, point q) {
		if (sgn(p - P[n + 1]) != sgn(q - P[n + 1])) return sgn(p - P[n + 1]);
		else return ccw(P[n + 1], p, q) > 0;
	});

	pointd R[2 * n];
	for (int i = 0; i < n; i++) {
		point v = (Q[i] - P[n + 1]) + (Q[(i + 1) % n] - P[n + 1]);

		// cout << "between " << "(" << Q[i].x << ", " << Q[i].y << ") and (" << Q[(i + 1) % n].x << ", " << Q[(i + 1) % n].y << ")\n";

		pii M = {-1, 0}; int p = -1;
		for (int j = 0; j < n; j++) {
			point q = P[j], r = P[(j + 1) % n];
			pii K = cross(P[n + 1], q, r, v);
			if (K.ff != -1) {
				if (M.ff == -1 || 1ll * M.ff * K.ss > 1ll * M.ss * K.ff) M = K, p = j;
			}
		}
		assert(p != -1);

		pii A = cross(P[n + 1], P[p], P[(p + 1) % n], Q[i] - P[n + 1]);
		pii B = cross(P[n + 1], P[p], P[(p + 1) % n], Q[(i + 1) % n] - P[n + 1]);

		// cout << A.ff << "/" << A.ss << " " << B.ff << "/" << B.ss << '\n';

		R[2 * i] = (ld)A.ff / A.ss * (Q[i] - P[n + 1]) + P[n + 1];
		R[2 * i + 1] = (ld)B.ff / B.ss * (Q[(i + 1) % n] - P[n + 1]) + P[n + 1];
	
		// if (ccw(P[n + 1], R[2 * i], P[n]) && ccw(P[n + 1], P[n], R[2 * i + 1]) && ccw(R[2 * i], R[2 * i + 1], P[n]) >= 0) {
		// 	return !(cout << fixed << 0 << '\n');
		// }
	}
	// for (int i = 0; i < 2 * n; i++) {
	// 	cout << "(" << R[i].x << ", " << R[i].y << ")\n";
	// }

	vector<pair<pii, pointd>> V;
	for (int i = 0; i <= n; i++) for (int j = 0; j < i; j++) V.push_back({{i, j}, P[j]});
	for (int i = 0; i <= n; i++) for (int j = 0; j < 2 * n; j++) V.push_back({{i, n + 1}, R[j]});
	for (int i = 0; i <= n; i++) for (int j = 0; j < 2 * n; j++) {
		pointd q = R[j], r = R[(j + 1) % (2 * n)];
		if (abs((q - r) * (q - r)) < 1e-12) continue;

		bool flag = true;
		pointd h = hypot(q, r, P[i], flag);
		if (flag) V.push_back({{i, n + 1}, h});
	}

	for (auto [pr, s] : V) {
		auto [i, j] = pr;
		pointd p = P[i];

		vector<ld> A = {0, 1};
		for (int k = 0; k < n; k++) {
			pointd q = P[k], r = P[(k + 1) % n];
			bool f = cross(p, s, q, r);
			if (f) {
				A.push_back(intersect(p, s - p, q, r - q));
			}
		}
		sort(A.begin(), A.end());

		int sz = A.size();
		bool flag = true;
		for (int k = 0; k < sz - 1; k++) {
			ld K = 0.5 * (A[k + 1] + A[k]);
			pointd m = p + K * (s - p);
			if (!polygon_in(m)) {
				flag = false;
				break;
			}
		}
		if (flag) {
			ld d = sqrtl((s - p) * (s - p));
			// cout << "edge between " << i << " and " << j << " -> " << d << '\n';
			G[i].push_back({d, j});
			G[j].push_back({d, i});
		}
	}

	fill(ds, ds + SZ, 1e18);
	priority_queue<pair<ld, int>> pq;
	ds[n] = 0;
	pq.push({0, n});
	while (!pq.empty()) {
		auto [d, v] = pq.top(); pq.pop();
		if (ds[v] != -d) continue;
		for (auto [w, x] : G[v]) {
			if (ds[x] > ds[v] + w) {
				ds[x] = ds[v] + w;
				pq.push({-ds[x], x});
			}
		}
	}
	cout << fixed << ds[n + 1] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4152kb

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:

29.0000000000

result:

ok found '29.0000000', expected '29.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

16
39 2
48 22
39 41
20 51
20 68
40 66
20 80
20 98
38 117
5 100
13 73
7 49
19 39
20 23
20 20
7 13
20 10
20 104

output:

13.0000000000

result:

ok found '13.0000000', expected '13.0000000', error '0.0000000'

Test #3:

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

input:

16
13 33
20 60
23 66
39 97
49 105
73 166
100 205
117 272
98 216
80 180
66 172
68 156
51 122
41 121
22 92
2 44
10 40
104 228

output:

140.8722825825

result:

ok found '140.8722826', expected '140.8722826', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 4084kb

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
81 12
33 23

output:

64.2045377025

result:

ok found '64.2045377', expected '64.2045377', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4144kb

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
33 23
81 12

output:

72.2834980412

result:

ok found '72.2834980', expected '72.2834980', error '0.0000000'

Test #6:

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

input:

7
76 8
389 215
691 19
407 331
489 397
300 403
363 334
126 60
393 370

output:

6.6579177565

result:

ok found '6.6579178', expected '6.6579178', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 4008kb

input:

3
0 1000
1000 0
1000 1000
567 578
589 601

output:

102.5304832720

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '102.5304833', error = '102.5304833'