QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326158#3184. Around the Trackcrimson231AC ✓8ms4084kbC++207.2kb2024-02-12 13:54:232024-02-12 13:54:23

Judging History

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

  • [2024-02-12 13:54:23]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:4084kb
  • [2024-02-12 13:54:23]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>;
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld TOL = 1e-8;
const ld INF = 1e17;
const int LEN = 50;
int N, M, t;
ld G[LEN << 1][LEN << 1];

struct Info {
	int i;
	ld c;
	bool operator < (const Info& x) const { return c > x.c; }
};
//std::priority_queue<Info> Q;
//ld COST[LEN << 1];
//ld dijkstra(int v, int g) {
//	for (int i = 0; i < LEN << 1; 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 (int j = 0; j < t; j++) {
//			ld w = G[p.i][j];
//			if (w > 1e16) continue;
//			ld cost = p.c + w;
//			if (COST[j] > cost) {
//				COST[j] = cost;
//				Q.push({ j, cost });
//			}
//		}
//	}
//	return COST[g];
//}
void floyd_warshall() {
	//for (int k = 0; k < t; k++) {
	//	for (int i = 0; i < t; i++) {
	//		for (int j = 0; j < t; j++) {
	//			G[i][j] = std::min(G[i][k] + G[k][j], G[i][j]);
	//		}
	//	}
	//}
	for (int k = 0; k < t; k++) {
		for (int i = 0; i < t; i++) {
			for (int j = i + 1; j < t; j++) {
				if (k != i && k != j) {
					G[i][j] = std::min(G[i][k] + G[k][j], G[i][j]);
					G[j][i] = std::min(G[j][k] + G[k][i], G[j][i]);
				}
			}
		}
	}
	return;
}
bool z(const ld& x) { return std::abs(x) < TOL; }
struct Pos {
	ld x, y;
	int i;
	Pos(ld X = 0, ld Y = 0, int I = 0) : x(X), y(Y), i(I) {}
	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, i }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y, i }; }
	Pos operator * (const ld& n) const { return { x * n, y * n, i }; }
	Pos operator / (const ld& n) const { return { x / n, y / n, i }; }
	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, i }; }
	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); }
} inner[LEN], outer[LEN], nodes[LEN << 1];
std::vector<Pos> C, H;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
ld dot(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;
}
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) {
	ld ret = dot(d1, d3, d2);
	return !ccw(d1, d2, d3) && (ret > 0 || z(ret));
}
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) {
	ld ret = dot(d1, d3, d2);
	return !ccw(d1, d2, d3) && ret > 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)) return 1;
		if (z(cur.y - nxt.y)) 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;
	//bool f3 = on_seg_strong(s1, s2, p1) ||
	//	on_seg_strong(s1, s2, p2) ||
	//	on_seg_strong(p1, p2, s1) ||
	//	on_seg_strong(p1, p2, s2);
	return (f1 && f2);// || f3;
}
bool blocked(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2) {
	bool f0 = intersect(s1, s2, d1, d2);
	bool f4 = on_seg_weak(s1, s2, d1) || on_seg_weak(s1, s2, d2);
	return f0 || f4;
}
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;
}
void monotone_chain(std::vector<Pos>& C, std::vector<Pos>& H) {
	std::sort(C.begin(), C.end());
	if (C.size() <= 2) {
		for (const Pos& p : C) H.push_back(p);
		return;
	}
	for (int i = 0; i < C.size(); i++) {
		while (H.size() > 1 && (cross(H[H.size() - 2], H[H.size() - 1], C[i]) < 0 || z(cross(H[H.size() - 2], H[H.size() - 1], C[i])))) {
			H.pop_back();
		}
		H.push_back(C[i]);
	}
	H.pop_back();
	int s = H.size() + 1;
	for (int i = C.size() - 1; i >= 0; i--) {
		while (H.size() > s && (cross(H[H.size() - 2], H[H.size() - 1], C[i]) < 0 || z(cross(H[H.size() - 2], H[H.size() - 1], C[i])))) {
			H.pop_back();
		}
		H.push_back(C[i]);
	}
	H.pop_back();
	return;
}
bool connectable(const int& i, const int& j) {
	return !blocked(outer, M, nodes[i], nodes[j])
		&& !blocked(inner, N, nodes[i], nodes[j])
		&& inner_check(outer, M, (nodes[i] + nodes[j]) * .5)
		&& !inner_check(inner, N, (nodes[i] + nodes[j]) * .5);
}
void init() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(9);
	t = 0;
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::cin >> inner[i].x >> inner[i].y;
		inner[i].i = t;
		nodes[t] = inner[i];
		t++;
	}
	std::cin >> M;
	for (int j = 0; j < M; j++) {
		std::cin >> outer[j].x >> outer[j].y;
		outer[j].i = t;
		nodes[t] = outer[j];
		t++;
	}
	C.resize(N);
	for (int i = 0; i < N; i++) C[i] = inner[i];
	monotone_chain(C, H);
	return;
}
void solve() {
	for (int i = 0; i < t; i++) for (int j = 0; j < t; j++) G[i][j] = INF;
	for (int i = 0; i < N; i++) {
		G[i][(i + 1) % N] = (inner[i] - inner[(i + 1) % N]).mag();
		for (int k = 0; k < t; k++) {
			if ((ccw(inner[i], inner[(i + 1) % N], nodes[k]) > 0
				|| on_seg_weak(inner[i], nodes[k], inner[(i + 1) % N]))
				&& connectable((i + 1) % N, k)) {
				G[(i + 1) % N][k] = (inner[(i + 1) % N] - nodes[k]).mag();
			}
		}
	}
	for (int j = 0; j < M; j++) {
		G[j + N][((j + 1) % M) + N] = (outer[j] - outer[(j + 1) % M]).mag();
		for (int k = 0; k < t; k++) {
			if ((ccw(outer[j], outer[(j + 1) % M], nodes[k]) < 0
				|| on_seg_weak(outer[j], nodes[k], outer[(j + 1) % M]))
				&& connectable(((j + 1) % M) + N, k)) {
				G[((j + 1) % M) + N][k] = (outer[(j + 1) % M] - nodes[k]).mag();
			}
		}
	}
	ld length = 0;
	int sz = H.size();

	//int s = H[0].i, e = H[sz - 1].i;
	//ld a = dijkstra(s, e), b = dijkstra(e, s);
	//length = a + b;

	floyd_warshall();
	for (int i = 0; i < sz; i++) {
		Pos cur = H[i], nxt = H[(i + 1) % sz];
		if (!blocked(outer, M, cur, nxt)) length += (cur - nxt).mag();
		else length += G[cur.i][nxt.i];
	}

	std::cout << length << "\n";
	return;
}
int main() { init(); solve(); return 0; }//boj10518

/*

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 6
10 3
9 6
8 5
7 6
6 3
5 6
4 4
3 8
0 8
43.6832385

7
1 1
5 1
5 19
4 2
3 18
2 2
1 19
9
0 0
6 0
6 20
5 20
4 3
3 19
2 3
1 20
0 20
102.129031841

4
-1000 -1000
0 0
1000 -1000
0 2000

8
1500 -1500
0 2500
-1500 -1500
-460 -730
-20 -510
0 -500
20 -510
460 -730
8560.6232978

*/

詳細信息

Test #1:

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

input:

3
1 1
2 1
1 2
3
0 0
4 0
0 4

output:

3.414213562

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #2:

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

input:

5
1 1
5 1
5 5
3 3
1 5
4
0 0
6 0
6 6
0 6

output:

16.000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #3:

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

input:

5
1 1
5 1
5 5
3 3
1 5
5
0 0
6 0
6 6
3 4
0 6

output:

16.472135955

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #4:

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

input:

5
2 2
6 2
6 6
4 4
2 6
4
0 0
8 0
8 8
0 8

output:

16.000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #5:

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

input:

5
2 2
6 2
6 6
4 4
2 6
5
0 0
8 0
8 8
4 5
0 8

output:

16.472135955

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #6:

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

input:

12
1 1
1 4
-1 4
-1 1
-4 1
-4 -1
-1 -1
-1 -4
1 -4
1 -1
4 -1
4 1
12
2 2
2 5
-2 5
-2 2
-5 2
-5 -2
-2 -2
-2 -5
2 -5
2 -2
5 -2
5 2

output:

25.888543820

result:

ok found '25.8885438', expected '25.8885438', error '0.0000000'

Test #7:

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

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 6
10 3
9 6
8 5
7 6
6 3
5 6
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #8:

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

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 8
10 3
9 8
8 5
7 8
6 3
5 8
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #9:

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

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 7
10 3
9 7
8 5
7 7
6 3
5 7
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #10:

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

input:

12
1 1
10 1
10 6
9 6
9 2
6 2
6 4
5 4
5 2
2 2
2 6
1 6
12
0 0
11 0
11 7
8 7
8 3
7 3
7 5
4 5
4 3
3 3
3 7
0 7

output:

33.152982445

result:

ok found '33.1529824', expected '33.1529824', error '0.0000000'

Test #11:

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

input:

7
1 1
5 1
5 19
4 2
3 18
2 2
1 19
9
0 0
6 0
6 20
5 20
4 3
3 19
2 3
1 20
0 20

output:

102.129031841

result:

ok found '102.1290318', expected '102.1290318', error '0.0000000'

Test #12:

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

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
16
0 0
13 0
13 9
4 9
4 4
5 4
5 8
10 8
10 3
9 3
9 7
6 7
6 3
3 3
3 6
0 6

output:

36.796691275

result:

ok found '36.7966913', expected '36.7966913', error '0.0000000'

Test #13:

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

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
12
0 0
13 0
13 9
4 9
4 4
5 4
5 8
6 8
6 3
3 3
3 6
0 6

output:

33.521451263

result:

ok found '33.5214513', expected '33.5214513', error '0.0000000'

Test #14:

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

input:

8
1 3
4 2
4 1
5 4
6 4
3 5
3 6
2 3
4
0 0
7 0
7 7
0 7

output:

14.422205102

result:

ok found '14.4222051', expected '14.4222051', error '0.0000000'

Test #15:

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

input:

8
1 2
2 1
4 3
4 5
5 5
4 6
2 4
2 2
4
2 0
6 4
4 7
0 3

output:

12.957417329

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #16:

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

input:

8
2 2
4 2
6 4
5 5
5 4
3 4
1 2
2 1
4
3 0
7 4
4 6
0 2

output:

12.957417329

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #17:

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

input:

12
1 3
4 2
9 2
9 1
10 4
10 9
11 9
8 10
3 10
3 11
2 8
2 3
4
0 3
9 0
12 9
3 12

output:

33.045188695

result:

ok found '33.0451887', expected '33.0451887', error '0.0000000'

Test #18:

score: 0
Accepted
time: 3ms
memory: 4080kb

input:

44
21 -7
21 5
20 5
20 -6
17 -6
17 4
16 4
16 -5
13 -5
13 3
12 3
12 -4
9 -4
9 2
8 2
8 -3
5 -3
5 1
4 1
4 -2
1 -2
1 0
-1 0
-1 -2
-4 -2
-4 1
-5 1
-5 -3
-8 -3
-8 2
-9 2
-9 -4
-12 -4
-12 3
-13 3
-13 -5
-16 -5
-16 4
-17 4
-17 -6
-20 -6
-20 5
-21 5
-21 -7
44
22 -8
22 6
19 6
19 -5
18 -5
18 5
15 5
15 -4
14 -4
...

output:

200.712066378

result:

ok found '200.7120664', expected '200.7120664', error '0.0000000'

Test #19:

score: 0
Accepted
time: 3ms
memory: 4084kb

input:

47
23 -13
22 11
21 -12
20 10
19 -11
18 9
17 -10
16 8
15 -9
14 7
13 -8
12 6
11 -7
10 5
9 -6
8 4
7 -5
6 3
5 -4
4 2
3 -3
2 1
1 -2
0 0
-1 -2
-2 1
-3 -3
-4 2
-5 -4
-6 3
-7 -5
-8 4
-9 -6
-10 5
-11 -7
-12 6
-13 -8
-14 7
-15 -9
-16 8
-17 -10
-18 9
-19 -11
-20 10
-21 -12
-22 11
-23 -13
47
24 -14
22 12
21 -11...

output:

603.514677955

result:

ok found '603.5146780', expected '603.5146780', error '0.0000000'

Test #20:

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

input:

8
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
0 10
-10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #21:

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

input:

8
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #22:

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

input:

8
10 0
10 10
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #23:

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

input:

8
0 -10
10 -10
10 0
10 10
0 10
-10 10
-10 0
-10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #24:

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

input:

4
-1000 -1000
0 0
1000 -1000
0 2000
50
1500 -1500
0 2500
-1500 -1500
-460 -730
-440 -720
-420 -710
-400 -700
-380 -690
-360 -680
-340 -670
-320 -660
-300 -650
-280 -640
-260 -630
-240 -620
-220 -610
-200 -600
-180 -590
-160 -580
-140 -570
-120 -560
-100 -550
-80 -540
-60 -530
-40 -520
-20 -510
0 -50...

output:

8560.623297837

result:

ok found '8560.6232978', expected '8560.6232978', error '0.0000000'

Test #25:

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

input:

4
-1 -1
1 -1
1 1
-1 1
16
1 3
-1 3
-1 2
-2 1
-3 1
-3 -1
-2 -1
-1 -2
-1 -3
1 -3
1 -2
2 -1
3 -1
3 1
2 1
1 2

output:

8.000000000

result:

ok found '8.0000000', expected '8.0000000', error '0.0000000'

Test #26:

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

input:

8
0 -1
3 -3
1 0
3 3
0 1
-3 3
-1 0
-3 -3
20
0 -2
7 -9
5 -6
6 -5
9 -7
2 0
9 7
6 5
5 6
7 9
0 2
-7 9
-5 6
-6 5
-9 7
-2 0
-9 -7
-6 -5
-5 -6
-7 -9

output:

25.298221281

result:

ok found '25.2982213', expected '25.2982213', error '0.0000000'

Test #27:

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

input:

5
5 5
3 3
1 5
1 1
5 1
5
0 0
6 0
6 6
3 4
0 6

output:

16.472135955

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #28:

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

input:

12
45 45
135 45
135 108
243 108
162 45
315 45
270 225
189 225
234 117
135 117
162 225
45 108
16
0 0
138 0
138 93
143 98
148 72
211 99
155 44
342 -45
360 270
180 270
192 125
175 122
169 125
161 270
0 180
0 90

output:

1158.353151750

result:

ok found '1158.3531518', expected '1158.3531517', error '0.0000000'

Test #29:

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

input:

4
-360 180
-297 270
-360 315
-405 225
6
-45 45
-270 270
-90 288
-90 450
-450 495
-540 135

output:

351.542597239

result:

ok found '351.5425972', expected '351.5425972', error '0.0000000'

Test #30:

score: 0
Accepted
time: 3ms
memory: 4024kb

input:

49
0 -1
460 -1
460 0
450 999
440 0
430 999
420 0
410 999
400 0
390 999
380 0
370 999
360 0
350 999
340 0
330 999
320 0
310 999
300 0
290 999
280 0
270 999
260 0
250 999
240 0
230 999
220 0
210 999
200 0
190 999
180 0
170 999
160 0
150 999
140 0
130 999
120 0
110 999
100 0
90 999
80 0
70 999
60 0
50 ...

output:

46374.304451082

result:

ok found '46374.3044511', expected '46374.3044511', error '0.0000000'

Test #31:

score: 0
Accepted
time: 3ms
memory: 4024kb

input:

50
-2255 1931
-2830 -3187
3406 -4113
-1883 -1838
2327 -1793
425 -1197
2782 -1197
-569 -601
-6 -1566
-1556 -1182
-793 124
3186 -187
481 523
1688 652
-1844 580
2726 1263
-1544 1419
2655 1961
-389 1916
2623 2899
-3785 4421
-4440 3211
-2902 3483
-4580 -3486
-2403 3382
-537 3211
425 2728
-1005 2345
-1696...

output:

67111.733745184

result:

ok found '67111.7337452', expected '67111.7337452', error '0.0000000'

Test #32:

score: 0
Accepted
time: 3ms
memory: 4028kb

input:

50
-4856 -2492
2539 -4838
4880 4847
-4864 -2066
2295 -4254
4404 4050
-4153 -1952
2123 -3843
3981 3355
-3486 -1880
1931 -3331
3514 2614
-2659 -1781
1764 -2833
3058 1817
-1907 -1667
1540 -2336
2515 1035
-1144 -1509
1404 -1895
2059 295
-389 -1338
1220 -1509
1540 -442
373 -1155
1084 -1167
661 -1083
1468...

output:

258611.429181497

result:

ok found '258611.4291815', expected '258611.4291815', error '0.0000000'

Test #33:

score: 0
Accepted
time: 3ms
memory: 3984kb

input:

50
1744 1847
-3538 3666
-3761 -4197
3609 -3486
4065 1874
1148 -2860
-1480 -3403
-2523 2444
-2299 -2917
-3050 -358
-2235 -3600
1456 -3046
3366 -160
3206 -3217
-3382 -3972
-2627 -3187
-3677 -3274
-3178 253
-2703 -571
-3370 3028
-2119 2800
-1068 -2548
2143 -912
-433 -643
-741 1521
-1037 -2420
-805 1646...

output:

55761.845617259

result:

ok found '55761.8456173', expected '55761.8456173', error '0.0000000'

Test #34:

score: 0
Accepted
time: 3ms
memory: 4020kb

input:

50
-4197 3951
885 2572
-3773 3127
-3294 -3459
-2710 2474
-2862 -3900
-3933 -3642
-4293 -4340
4392 -4355
-2255 -3786
-2235 2330
3374 1305
-1428 -3331
3026 340
3194 -3558
-1684 -3471
2822 1107
-1939 1889
-2011 -3558
4848 -4325
4373 4334
1104 1874
-2299 2486
-2363 -4128
-2607 2557
-2798 2587
-3286 -247...

output:

114150.091730721

result:

ok found '114150.0917307', expected '114150.0917307', error '0.0000000'

Test #35:

score: 0
Accepted
time: 4ms
memory: 4024kb

input:

50
-4704 -4583
2 4349
4616 -4667
2962 4706
-3697 4562
-4920 -4766
-805 -3984
-1080 -1224
417 -942
2091 -3729
-70 -2150
405 -3630
1456 -4340
2726 -4140
2411 -2860
1160 -885
142 -46
174 708
54 1206
-729 253
-421 -373
-1716 -472
-1005 978
-190 2018
301 1634
765 735
521 397
1033 10
1096 735
757 1832
46 ...

output:

43688.218484807

result:

ok found '43688.2184848', expected '43688.2184848', error '0.0000000'

Test #36:

score: 0
Accepted
time: 3ms
memory: 4024kb

input:

50
-4325 -4311
3769 3951
-3921 -4367
3470 2713
-3318 -4595
4752 -4526
661 -1212
4077 -4311
-2619 -4284
3270 -3915
-2351 -3942
2846 -3573
206 -1224
4213 2926
4712 -3999
861 -1011
4904 -4269
4680 4604
-2978 -3444
4572 4661
-4876 4691
-4792 -4481
-4684 4520
-4652 -4412
-4440 4406
4105 4478
-4229 4080
3...

output:

131797.092914833

result:

ok found '131797.0929148', expected '131797.0929148', error '0.0000000'

Test #37:

score: 0
Accepted
time: 8ms
memory: 4080kb

input:

50
-1400 0
900 1839
795 1976
682 2096
564 2197
440 2279
313 2340
182 2380
50 2399
-81 2396
-213 2373
-342 2327
-469 2262
-592 2176
-709 2070
-820 1946
-923 1805
-1019 1647
-1105 1475
-1181 1290
-1247 1093
-1302 886
-1345 671
-1376 451
-1394 226
-1401 0
-1394 -226
-1376 -451
-1345 -671
-1302 -886
-12...

output:

13435.252550644

result:

ok found '13435.2525506', expected '13435.2525506', error '0.0000000'

Test #38:

score: 0
Accepted
time: 2ms
memory: 4000kb

input:

50
-4832 -4823
-2311 4706
4784 -2435
-4600 -4640
-2183 4236
4137 -2321
-4313 -4311
-2075 3738
3514 -2177
-4061 -4041
-1971 3241
3162 -2093
-3877 -3858
-1883 2770
2750 -1964
-3665 -3642
-1800 2474
2251 -1838
-3382 -3346
-1696 2075
1772 -1724
-3138 -3145
-1620 1661
1360 -1622
-2922 -2890
1552 -1667
-1...

output:

30903.774376471

result:

ok found '30903.7743765', expected '30903.7743765', error '0.0000000'