QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323313#5104. Guardians of the Gallerycrimson231WA 89ms4144kbC++1411.9kb2024-02-09 09:07:452024-02-09 09:07:45

Judging History

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

  • [2024-02-09 09:07:45]
  • 评测
  • 测评结果：WA
  • 用时：89ms
  • 内存：4144kb
查看
  • [2024-02-09 09:07:45]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
typedef long double ld;
const ld TOL = 1e-8;
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;
			Pos cur = gallery[j], pre = gallery[(j + N - 1) % N], nxt = gallery[(j + 1) % N];
			last = rotate90(view_line, cur);
			inx = intersection(view_line, last);
			if (visible(gallery, N, cur, inx, sculpture))
				G[gallery[j].i].push_back({ 0, (cur - inx).mag() });
			last = L(cur, pre);
			inx = intersection(view_line, last);
			if (on_seg_weak(cur, pre, inx) && !invisible(gallery, N, inx, sculpture))
				G[gallery[j].i].push_back({ 0, (cur - inx).mag() });
			if (!blocked(gallery, N, guard, inx) && on_seg_weak(cur, pre, inx) && !invisible(gallery, N, inx, sculpture))
				G[guard.i].push_back({ 0, (guard - inx).mag() });
			last = L(cur, nxt);
			inx = intersection(view_line, last);
			if (on_seg_weak(cur, nxt, inx) && !invisible(gallery, N, inx, sculpture))
				G[gallery[j].i].push_back({ 0, (cur - inx).mag() });
			if (!blocked(gallery, N, guard, inx) && on_seg_weak(cur, nxt, inx) && !invisible(gallery, N, inx, sculpture))
				G[guard.i].push_back({ 0, (guard - inx).mag() });
		}
	}
	return;
}
void solve() { init(); std::cout << dijkstra(1, 0) << "\n"; return; }
int main() { solve(); return 0; }//boj26133


/*

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

140.8722826


8
10 10
40 25
20 25
20 35
12 23
30 23
10 20
5 40
15 15
19 26

25.0000000

*/

//ld cross(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) / (d4 - d3); }
//int ccw(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) {
//	ld ret = cross(d1, d2, d3, d4);
//	return z(ret) ? 0 : ret > 0 ? 1 : -1;
//}
//bool CW(const Line& l1, const Line& l2, const Line& target) {
//	if (l1.s / l2.s < TOL) return 0;
//	Pos p = intersection(l1, l2);
//	return target.s.vy * p.x + target.s.vx * p.y > target.c - TOL;
//}
//bool half_plane_intersection(std::vector<Line>& HP, std::vector<Pos>& hull) {
//	std::deque<Line> dq;
//	std::sort(HP.begin(), HP.end());
//	for (const Line& l : HP) {
//		if (!dq.empty() && z(dq.back() / l)) continue;
//		while (dq.size() >= 2 && CW(dq[dq.size() - 2], dq.back(), l)) dq.pop_back();
//		while (dq.size() >= 2 && CW(l, dq.front(), dq[1])) dq.pop_front();
//		dq.push_back(l);
//	}
//	while (dq.size() >= 3 && CW(dq[dq.size() - 2], dq.back(), dq.front())) dq.pop_back();
//	while (dq.size() >= 3 && CW(dq.back(), dq.front(), dq[1])) dq.pop_front();
//	for (int i = 0; i < dq.size(); i++) {
//		Line cur = dq[i], nxt = dq[(i + 1) % dq.size()];
//		if (cur / nxt < TOL) {
//			hull.clear();
//			return 0;
//		}
//		hull.push_back(intersection(cur, nxt));
//	}
//	return 1;
//}
//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;
//
//	t = 0;
//	nodes[t++] = sculpture;
//	nodes[t++] = guard;
//
//	Pos cost;
//	for (int i = 0; i < N; i++) nodes[t++] = gallery[i];
//	for (int i = 1; i < t; i++) {//O(N^3)
//		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)) {
//				cost = nodes[i] - nodes[j];
//				G[i].push_back({ j, cost.mag() });
//				G[j].push_back({ i, cost.mag() });
//			}
//		}
//	}
//	Line view_line, last;
//	Pos inx;
//	for (int i = 0; i < N; i++) {//O(N^3)
//		view_line = L(sculpture, gallery[i]);
//		last = rotate90(view_line, guard);
//		inx = intersection(view_line, last);
//		//if (inner_check(gallery, N, inx) 
//		//	&& !blocked(gallery, N, guard, inx) 
//		//	&& inner_check(gallery, N, (guard + inx) * .5) 
//		//	&& !invisible(gallery, N, inx, sculpture)) 
//		//		G[guard.i].push_back({ 0, (guard - inx).mag() });
//		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 (inner_check(gallery, N, inx) 
//			//	&& !blocked(gallery, N, gallery[j], inx) 
//			//	&& inner_check(gallery, N, (gallery[j] + inx) * .5) 
//			//	&& !invisible(gallery, N, inx, sculpture)) 
//			//		G[gallery[j].i].push_back({ 0, (gallery[j] - inx).mag() });
//			if (visible(gallery, N, gallery[j], inx, sculpture))
//					G[gallery[j].i].push_back({ 0, (gallery[j] - inx).mag() });
//		}
//	}
//	return;
//}
//bool inner_check(std::vector<Pos>& H, const Pos& p) {
//	int cnt = 0;
//	int sz = H.size();
//	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;
//}
源文件, 语言: C++14

详细

Test #1:

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

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: 2ms
memory: 4068kb

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

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: 1ms
memory: 4040kb

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

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

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

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

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

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

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: 0
Accepted
time: 0ms
memory: 4088kb

input:

8
10 10
40 25
20 25
20 35
12 23
30 23
10 20
5 40
15 15
19 26

output:

25.0000000

result:

ok found '25.0000000', expected '25.0000000', error '0.0000000'

Test #12:

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

input:

9
5 1000
6 3
5 999
0 1000
0 0
500 2
500 0
1000 0
1000 1000
1 4
993 1

output:

5.1010479

result:

ok found '5.1010479', expected '5.1010479', error '0.0000000'

Test #13:

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

input:

100
695 43
538 87
463 208
597 329
750 306
812 481
960 555
912 344
983 450
987 573
994 852
941 985
801 855
792 800
849 806
792 696
924 701
939 672
710 546
722 668
723 807
715 767
624 524
634 554
547 503
357 352
627 458
651 495
937 558
932 545
864 509
753 489
509 397
341 335
300 495
199 528
380 688
48...

output:

1695.1865730

result:

ok found '1695.1865730', expected '1695.1865730', error '0.0000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4044kb

input:

20
840 854
839 45
996 905
959 938
852 938
730 423
425 493
136 481
213 778
527 740
691 941
22 830
83 313
462 155
636 21
462 321
360 324
238 422
402 492
806 406
952 822
410 838

output:

1424.3842015

result:

ok found '1424.3842015', expected '1424.3842015', error '0.0000000'

Test #15:

score: -100
Wrong Answer
time: 41ms
memory: 4096kb

input:

74
89 395
52 622
124 832
115 698
95 598
199 491
190 356
191 398
132 315
94 371
34 221
91 0
153 139
220 465
260 283
312 30
409 15
338 50
343 52
437 69
359 89
332 213
377 505
375 396
405 199
657 90
658 50
360 50
618 23
642 7
824 191
688 417
795 227
709 286
662 321
646 175
485 210
381 357
420 329
441 3...

output:

2037.1787887

result:

wrong answer 1st numbers differ - expected: '2036.7557099', found: '2037.1787887', error = '0.0002077'
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:26:34 | 开源项目