QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387470 | #5104. Guardians of the Gallery | ucup-team1209# | WA | 1ms | 4092kb | C++20 | 4.6kb | 2024-04-12 15:32:54 | 2024-04-12 15:32:54 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int mod = 998244353;
const db eps = 1e-9;
const int N = 505;
using pr = std::pair<int, int>;
struct p2 {
db x, y;
db norm() const {
return x * x + y * y;
}
db abs() const {
return std::sqrt(norm());
}
};
p2 r90(p2 x) {
return {-x.y, x.x};
}
p2 operator + (p2 x, p2 y) { return {x.x + y.x, x.y + y.y}; }
p2 operator - (p2 x, p2 y) { return {x.x - y.x, x.y - y.y}; }
p2 operator * (p2 x, db y) { return {x.x * y, x.y * y}; }
db operator * (p2 x, p2 y) {
return x.x * y.y - x.y * y.x;
}
db operator % (p2 x, p2 y) {
return x.x * y.x + x.y * y.y;
}
int half(p2 x) {
return x.y < -eps || (std::fabs(x.y) < eps & x.x < eps);
}
int cmp(p2 a, p2 b) {
return half(a) == half(b) ? a * b > 0 : half(b);
}
int cmp_eq(p2 A, p2 B) {
return half(A) == half(B) && fabs(A * B) < eps;
}
bool operator == (p2 x, p2 y) {
return fabs(x.x - y.x) < eps && fabs(x.y - y.y) < eps;
}
bool operator != (p2 x, p2 y) {
return fabs(x.x - y.x) > eps || fabs(x.y - y.y) > eps;
}
struct seg {
p2 x, y;
p2 f() {
p2 r = r90(x - y);
db rr = r.abs();
r.x /= rr;
r.y /= rr;
return r;
}
p2 proj(p2 o) {
db X = (x - o) * (y - o) / (x - y).abs();
return o + f() * X;
}
db onseg(p2 o) {
return (o - x) % (o - y) < eps;
}
};
db sgn(db x) {
return x < -eps ? -1 : x > eps;
}
int ccw(p2 a, p2 b, p2 c) {
int sign = sgn((b - a) * (c - a));
if(sign == 0) {
if(sgn((b - a) % (c - a)) == -1) return 2;
if((c - a).norm() > (b - a).norm() + eps) return -2;
}
return sign;
}
bool is_isc(const seg & x, const seg & y) {
return ccw(x.x, y.y, y.x) * ccw(x.x, x.y, y.y) <= 0 &&
ccw(y.x, y.y, x.x) * ccw(y.x, y.y, x.y) <= 0;
}
int n;
p2 a[N];
std::vector<p2> v;
p2 start, goal;
bool contains(seg x) {
p2 t = x.y - x.x; db tr = t.abs();
t.x /= tr, t.y /= tr;
std::vector<std::pair<db, int>> V;
for(int i = 0;i < n;++i) {
p2 u = a[i], v = a[(i + 1) % n];
u = u - x.x;
v = v - x.x;
int du = sgn(u * t), dv = sgn(v * t);
if(du != dv) {
p2 delta = v - u;
db inc = (u * t) / (delta * t);
V.emplace_back((u - delta * inc) % t, du - dv);
}
}
db L = 0, R = (x.y - x.x) % t;
V.emplace_back(-1e5, 0);
V.emplace_back(1e5, 0);
sort(V.begin(), V.end());
int sum = 0;
for(int i = 0;i + 1 < (int) V.size();++i) {
sum += V[i].second;
if(sum == 0) {
db l = V[i].first, r = V[i + 1].first;
db len = std::min(r, R) - std::max(l, L);
if(len > eps) return 0;
}
}
return 1;
}
db e[N][N];
int main() {
#ifdef zqj
freopen("$.in", "r", stdin);
#endif
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 0;i < n;++i) {
cin >> a[i].x >> a[i].y;
}
cin >> start.x >> start.y;
cin >> goal.x >> goal.y;
start = start - goal;
for(int i = 0;i < n;++i) {
a[i] = a[i] - goal;
}
goal = {0, 0};
std::vector<p2> v(a, a + n);
std::vector<seg> segs;
for(int i = 0;i < n;++i) {
segs.push_back({a[i], a[(i + 1) % n]});
}
sort(v.begin(), v.end(), cmp);
auto vv = v;
vv.erase(unique(vv.begin(), vv.end(), cmp_eq), vv.end());
p2 F = {1e5, 1e5};
std::vector<p2> l(vv.size(), F), r(l);
for(auto [x, y] : segs) {
if(x * y < 0) std::swap(x, y);
if(sgn(x * y) == 0) {
continue;
}
int L = lower_bound(vv.begin(), vv.end(), x, cmp) - vv.begin();
int R = lower_bound(vv.begin(), vv.end(), y, cmp) - vv.begin();
if(x.norm() < r[L].norm()) {
r[L] = x;
}
if(y.norm() < l[R].norm()) {
l[R] = y;
}
}
std::vector<p2> p;
for(int i = 0;i < (int) vv.size();++i) {
if(l[i] != F && contains({goal, l[i]})) p.push_back(l[i]);
if(r[i] != F && r[i] != F && contains({goal, r[i]})) p.push_back(r[i]);
}
auto A = v;
A.insert(A.end(), p.begin(), p.end());
A.push_back(start);
A.push_back(goal);
int N = A.size();
for(int i = 0;i < N;++i) {
for(int j = 0;j < N;++j) {
if(contains({A[i], A[j]})) {
e[i][j] = (A[i] - A[j]).abs();
} else {
e[i][j] = 1e18;
}
}
}
for(int i = 0;i < N;++i) {
for(int j = 0;j < N;++j) {
for(int k = 0;k < N;++k) {
e[j][k] = std::min(e[j][k], e[j][i] + e[i][k]);
}
}
}
int st = find(A.begin(), A.end(), start) - A.begin();
db ans = 1e18;
for(int i = 0;i < N;++i) {
for(int j = 0;j < (int) p.size();++j) {
seg S {p[j], p[(j + 1) % p.size()]};
p2 p = S.proj(A[i]);
if(S.onseg(p)) {
if(contains({A[i], p})) {
ans = std::min(ans, e[st][i] + (A[i] - p).abs());
}
}
}
}
printf("%.20lf\n", ans);
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4092kb
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:
43.41983504804584725889
result:
wrong answer 1st numbers differ - expected: '29.0000000', found: '43.4198350', error = '0.4972357'