QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323307 | #5104. Guardians of the Gallery | crimson231 | WA | 1ms | 4012kb | C++14 | 7.1kb | 2024-02-09 08:19:51 | 2024-02-09 08:19:51 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
typedef long double ld;
const ld TOL = 1e-7;
const ld INF = 1e17;
const int LEN = 102;
int N, t{ 0 };
ld COST[LEN];
struct Info {
int i;
ld c;
bool operator < (const Info& x) const { return c > x.c; }
};
std::vector<Info> G[LEN];
std::priority_queue<Info> Q;
ld dijkstra(int v, int g) {
for (int i = 0; i < LEN; i++) COST[i] = INF;
Q.push({ v, 0 });
COST[v] = 0;
while (Q.size()) {
Info p = Q.top(); Q.pop();
if (p.c > COST[p.i]) continue;
for (const Info& w : G[p.i]) {
ld cost = p.c + w.c;
if (COST[w.i] > cost) {
COST[w.i] = cost;
Q.push({ w.i, cost });
}
}
}
return COST[g];
}
bool z(const ld& x) { return std::abs(x) < TOL; }
struct Pos {
ld x, y;
int i;
Pos(ld X, ld Y, int I) : x(X), y(Y), i(I) {}
Pos() : x(0), y(0), i(0) {}
bool operator == (const Pos& p) const { return z(x - p.x) && z(y - p.y); }
bool operator < (const Pos& p) const { return z(x - p.x) ? y < p.y : x < p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y, 0 }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y, 0 }; }
Pos operator * (const ld& n) const { return { x * n, y * n, 0 }; }
Pos operator / (const ld& n) const { return { x / n, y / n, 0 }; }
ld operator * (const Pos& p) const { return { x * p.x + y * p.y }; }
ld operator / (const Pos& p) const { return { x * p.y - y * p.x }; }
Pos operator ~ () const { return { -y, x, 0 }; }
ld operator ! () const { return x * y; }
Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
Pos& operator *= (const ld& scale) { x *= scale; y *= scale; return *this; }
ld mag() const { return hypot(x, y); }
} gallery[LEN], nodes[LEN], sculpture{ 0, 0, 0 }, guard{ 0, 0, 1 };// const Pos O = { 0, 0, -1 };
struct Vec {
ld vy, vx;
bool operator < (const Vec& v) const { return z(vy - v.vy) ? vx < v.vx : vy < v.vy; }
bool operator == (const Vec& v) const { return (z(vy - v.vy) && z(vx - v.vx)); }
ld operator / (const Vec& v) const { return vy * v.vx - vx * v.vy; }
Vec operator ~ () const { return { -vx, vy }; }
}; const Vec Zero = { 0, 0 };
struct Line {
Vec s;
ld c;
bool operator < (const Line& l) const {
bool f1 = Zero < s;
bool f2 = Zero < l.s;
if (f1 != f2) return f1;
ld ccw = s / l.s;
return z(ccw) ? c * hypot(l.s.vy, l.s.vx) < l.c * hypot(s.vy, s.vx) : ccw > 0;
}
ld operator / (const Line& l) const { return s / l.s; }
};
Line L(const Pos& s, const Pos& e) {
ld dy, dx, c;
dy = e.y - s.y;
dx = s.x - e.x;
c = dy * s.x + dx * s.y;
return { { dy, dx } , c };
}
Line rotate90(const Line& l, const Pos& p) {
Vec s = ~l.s;
ld c = s.vy * p.x + s.vx * p.y;
return { s, c };
}
Pos intersection(const Line& l1, const Line& l2) {
Vec v1 = l1.s, v2 = l2.s;
ld det = v1 / v2;
return {
(l1.c * v2.vx - l2.c * v1.vx) / det,
(l2.c * v1.vy - l1.c * v2.vy) / det,
0
};
}
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) {
ld ret = cross(d1, d2, d3);
return z(ret) ? 0 : ret > 0 ? 1 : -1;
}
ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) {
ld dot_ = dot(d1, d3, d2);
return z(cross(d1, d2, d3)) && (dot_ > 0 || z(dot_));
}
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) {
ld dot_ = dot(d1, d3, d2);
return z(cross(d1, d2, d3)) && dot_ > 0;
}
bool inner_check(Pos H[], const int& sz, const Pos& p) {
int cnt = 0;
for (int i = 0; i < sz; i++) {
Pos cur = H[i], nxt = H[(i + 1) % sz];
//if (on_seg_strong(cur, nxt, p)) continue;
if (on_seg_strong(cur, nxt, p)) return 1;
if (z(cur.y - nxt.y)) continue;
//if (cur.x < p.x && nxt.x < p.x) continue;
if (nxt.y < cur.y) std::swap(cur, nxt);
if (nxt.y - TOL < p.y || cur.y > p.y) continue;
cnt += ccw(cur, nxt, p) > 0;
}
return cnt & 1;
}
bool intersect(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2) {
bool f1 = ccw(s1, s2, d1) * ccw(s2, s1, d2) > 0;
bool f2 = ccw(d1, d2, s1) * ccw(d2, d1, s2) > 0;
return f1 && f2;
}
bool blocked(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2) {
bool f1 = ccw(s1, s2, d1) * ccw(s2, s1, d2) > 0;
bool f2 = ccw(d1, d2, s1) * ccw(d2, d1, s2) > 0;
bool f3 = on_seg_weak(s1, s2, d1) || on_seg_weak(s1, s2, d2);
return (f1 && f2) || f3;
}
bool blocked(Pos H[], const int& sz, const Pos& s1, const Pos& s2) {
for (int i = 0; i < sz; i++) if (blocked(s1, s2, H[i], H[(i + 1) % sz])) return 1;
return 0;
}
bool invisible(Pos H[], const int& sz, const Pos& p, const Pos& target) {
bool l{ 0 }, r{ 0 };
for (int i = 0; i < sz; i++) {
Pos cur = H[i], nxt = H[(i + 1) % sz];
if (!ccw(p, target, cur) && !ccw(p, target, nxt)) continue;
if (intersect(p, target, cur, nxt)) return 1;
if (on_seg_weak(p, target, cur) && ccw(p, target, nxt) > 0) l = 1;
if (on_seg_weak(p, target, nxt) && ccw(p, target, cur) > 0) l = 1;
if (on_seg_weak(p, target, cur) && ccw(p, target, nxt) < 0) r = 1;
if (on_seg_weak(p, target, nxt) && ccw(p, target, cur) < 0) r = 1;
if (l && r) return 1;
}
//return l && r;
return 0;
}
bool visible(Pos H[], const int& sz, const Pos& p, const Pos& inx, const Pos& target) {
return inner_check(H, sz, inx) && !blocked(H, sz, p, inx) && inner_check(H, sz, (p + inx) * .5) && !invisible(H, sz, inx, target);
}
void init() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(7);
std::cin >> N;
for (int i = 0; i < N; i++) std::cin >> gallery[i].x >> gallery[i].y, gallery[i].i = i + 2;
std::cin >> guard.x >> guard.y >> sculpture.x >> sculpture.y;
sculpture.i = 0;
guard.i = 1;
if (!invisible(gallery, N, guard, sculpture)) { G[1].push_back({ 0, 0 }); return; }
t = 0;
nodes[t++] = sculpture;
nodes[t++] = guard;
Pos seg;
for (int i = 0; i < N; i++) nodes[t++] = gallery[i];
for (int i = 1; i < t; i++) {
if (!invisible(gallery, N, nodes[i], nodes[0])) G[i].push_back({ 0, 0 });
for (int j = i + 1; j < t; j++) {
if (!blocked(gallery, N, nodes[i], nodes[j])
&& inner_check(gallery, N, (nodes[i] + nodes[j]) * .5)) {
seg = nodes[i] - nodes[j];
G[i].push_back({ j, seg.mag() });
G[j].push_back({ i, seg.mag() });
}
}
}
Line view_line, last;
Pos inx;
for (int i = 0; i < N; i++) {
view_line = L(sculpture, gallery[i]);
last = rotate90(view_line, guard);
inx = intersection(view_line, last);
if (visible(gallery, N, guard, inx, sculpture))
G[guard.i].push_back({ 0, (guard - inx).mag() });
for (int j = 0; j < N; j++) {
if (i == j) continue;
last = rotate90(view_line, gallery[j]);
inx = intersection(view_line, last);
if (visible(gallery, N, gallery[j], inx, sculpture))
G[gallery[j].i].push_back({ 0, (gallery[j] - inx).mag() });
}
}
return;
}
void solve() { init(); std::cout << dijkstra(1, 0) << "\n"; return; }
int main() { solve(); return 0; }//boj26133
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3964kb
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.0000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3940kb
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.0000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3996kb
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.8722826
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3912kb
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.2045377
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3976kb
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.2834980
result:
ok found '72.2834980', expected '72.2834980', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
7 76 8 389 215 691 19 407 331 489 397 300 403 363 334 126 60 393 370
output:
6.6579178
result:
ok found '6.6579178', expected '6.6579178', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
3 0 1000 1000 0 1000 1000 567 578 589 601
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 0 1000 0 0 1000 0 366 366 367 366
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
5 50 93 278 178 199 300 596 362 208 519 421 388 142 153
output:
175.1697594
result:
ok found '175.1697594', expected '175.1697594', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
7 50 93 278 178 199 300 401 312 483 162 596 362 208 519 488 252 142 153
output:
289.6821399
result:
ok found '289.6821399', expected '289.6821399', error '0.0000000'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3908kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
27.1980390
result:
wrong answer 1st numbers differ - expected: '25.0000000', found: '27.1980390', error = '0.0879216'