QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323235#5104. Guardians of the Gallerycrimson231WA 1ms4088kbC++147.0kb2024-02-09 00:03:542024-02-09 00:03:54

Judging History

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

  • [2024-02-09 00:03:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4088kb
  • [2024-02-09 00:03:54]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 4088kb

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: -100
Wrong Answer
time: 1ms
memory: 3992kb

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:

144.2854439

result:

wrong answer 1st numbers differ - expected: '140.8722826', found: '144.2854439', error = '0.0242288'