QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#465445 | #5104. Guardians of the Gallery | karuna | WA | 2ms | 4152kb | C++20 | 6.2kb | 2024-07-06 21:58:54 | 2024-07-06 21:58:55 |
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;
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'