QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#450341#4628. Driverless Car IIskip2004AC ✓3763ms4484kbC++206.1kb2024-06-22 10:30:052024-06-22 10:30:05

Judging History

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

  • [2024-06-22 10:30:05]
  • 评测
  • 测评结果:AC
  • 用时:3763ms
  • 内存:4484kb
  • [2024-06-22 10:30:05]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
const int N = 1000005;
using u64 = unsigned long long;
int n;
using db = double;
const db eps = 1e-8;
const db pi = std::acos(-1);
db sgn(db x) { return x < -eps ? -1 : x > eps; }
db eq(db x, db y) { return !sgn(x - y); }
struct p2 {
	db x, y;

	db norm() const { return x * x + y * y; }
	db abs() const { return std::sqrt(x * x + y * y); }
	db arg() const { return atan2(y, x); }
};
db arg(p2 x, p2 y) {
	db a = y.arg() - x.arg();
	if(a > pi) a -= pi * 2;
	if(a < -pi) a += pi * 2;
	return a;
}
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}; }
p2 operator * (p2 x, db y) { return {x.x * y, x.y * y}; }
p2 operator * (db y, p2 x) { 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; }
struct line : p2 {
	db z;
	int id;
	// a * x + b * y + c (= or >) 0
	line() = default;
	line(db a, db b, db c) : p2{a, b}, z(c), id(-1) {}
	line(p2 a, p2 b) : p2(r90(b - a)), z(a * b), id(-1) { } //左侧 > 0
	db operator ()(p2 a) const { return a % p2(*this) + z; }
	line perp() const { return {y, -x, 0}; } // 垂直
	line para(p2 o) { return {x, y, z - (*this)(o)}; } // 平行
};
p2 operator & (line x, line y) {
	return p2{p2{x.z, x.y} * p2{y.z, y.y}, p2{x.x, x.z} * p2{y.x, y.z}} / -(p2(x) * p2(y));
	// 注意此处精度误差较大,以及 res.y 需要较高精度
}
p2 proj(p2 x, line l){return x - p2(l) * (l(x) / l.norm());}//投影
p2 refl(p2 x, line l){return x - p2(l) * (l(x) / l.norm()) * 2;}//对称
db dist(line l, p2 x={0, 0}){return l(x) / l.abs();}//有向点到线距离
bool is_para(line x, line y){return eq(p2(x) * p2(y), 0);}//判断线平行
bool is_perp(line x, line y){return eq(p2(x) % p2(y), 0);}//判断线垂直
bool online(p2 x, line l) { return eq(l(x), 0); } // 判断点在线上
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;
}
db det(line a, line b, line c) {
	p2 A = a, B = b, C = c;
	return c.z * (A * B) + a.z * (B * C) + b.z * (C * A);
}
db check(line a, line b, line c) { // sgn same as c(a & b), 0 if error
	return sgn(det(a, b, c)) * sgn(p2(a) * p2(b));
}
bool paraS(line a, line b) { // 射线同向
	return is_para(a, b) && p2(a) % p2(b) > 0;
}
std::vector<line> cut(const std::vector<line> & o, line l) {
	std::vector<line> res;
	int n = size(o);
	for(int i = 0;i < n;++i) {
		line a = o[i], b = o[(i + 1) % n], c = o[(i + 2) % n];
		int va = check(a, b, l), vb = check(b, c, l);
		if(va > 0 || vb > 0 || (va == 0 && vb == 0)) {
			res.push_back(b);
		}
		if(va >= 0 && vb < 0) {
			res.push_back(l);
		}
	}
	if(res.size() <= 2) return {};
	return res;
} // 切凸包
struct seg {
	p2 x, y;
	seg() {}
	seg(const p2 & A, const p2 & B) : x(A), y(B) {}
	bool onseg(const p2 & o) const {
		return (o - x) % (o - y) < eps;
	}
	line to_l() const { return line(x, y); }
};
struct circle : p2 { db r; };
std::vector<p2> operator & (circle o, line l) {
	p2 v = l, Rv = r90(v); db L = l.abs();
	db d = l(p2(o)) / L, x = o.r * o.r - d * d;
	if(x < -eps) return {};
	x = std::sqrt(x * sgn(x));
	p2 z = p2(o) - v * (d / L), p = Rv * (x / L);
	return {z + p, z - p};
} // l 如果是构造函数给出,那么返回交点按射线顺序
std::vector<p2> operator & (circle o, seg s) {
	std::vector<p2> b;
	for(p2 x : (o & s.to_l()))
		if(s.onseg(x)) b.push_back(x);
	return b;
}
std::vector<p2> operator & (circle o0, circle o1) {
	p2 tmp = (p2(o1) - p2(o0)) * 2.;
	return o0 & line(tmp.x, tmp.y, o1.r * o1.r - o0.r * o0.r + o0.norm() - o1.norm());
}
std::vector<p2> tang(circle o, p2 x) {
	db d = (x - p2(o)).abs();
	if(d <= o.r + eps) return {};
	return o & circle{x, sqrt(d * d - o.r * o.r)};
}
// 三角形 (0, a, b) 和圆 o 的交的有向面积 * 2
db intersect(circle o, p2 a, p2 b) {
	a = a - p2(o), b = b - p2(o); o.x = o.y = 0;
	int va = a.abs() <= o.r + eps;
	int vb = b.abs() <= o.r + eps;
	if(va && vb) return a * b;
	auto v = o & seg{a, b}; // 注意这里,有必要改一下 onseg,去掉平行判定
	if(v.empty()) return arg(a, b) * o.r * o.r;
	db sum = 0;
	sum += va ? a * v[0] : arg(a, v[0]) * o.r * o.r;
	sum += vb ? v.back() * b : arg(v.back(), b) * o.r * o.r;
	if(v.size() > 1) sum += v[0] * v[1];
	return sum;
}
line bisector(p2 a, p2 b) { return line(a.x - b.x, a.y - b.y, (b.norm() - a.norm()) / 2); }

int main() {
	int n, k;
	cin >> n >> k;
	std::vector<p2> a(n);
	for(auto & [x, y] : a) {
		cin >> x >> y;
	}
	shuffle(a.begin(), a.end(), std::mt19937_64(12421));
	const db V = 1e5;
	db ans = 0;
	for(int i = 0;i < n;++i) {
		std::vector<line> c = {
				{V, 0, V * V}, {0, V, V * V},
				{-V, 0, V * V}, {0, -V, V * V},
				};
		for(int j = 0;j < n;++j) {
			if(i == j) continue;
			p2 x = a[j];
			line l = bisector(a[i], x);
			l.id = j;
			c = cut(c, l);
		}
		for(int l = 0;l < (int) c.size();++l) {
			if(c[l].id != -1) {
				auto t = c;
				int xid = c[l].id;
				for(int j = 0;j < n;++j) {
					p2 x = a[j];
					if(xid == j || i == j) {
						continue;
					}
					line l = bisector(a[xid], x);
					t = cut(t, l);
				}
				p2 A = a[i], B = a[xid];
				if((A - B).abs() >= k) continue;
				p2 o = (A + B) / 2;
				p2 dx = B - o; dx = dx / dx.abs();
				p2 dy = r90(dx);
				p2 c1 = o + dx * k / 2;
				p2 c2 = o;
				db rr = k;
				for(int c = 50;c >= 0;--c) {
					rr /= 2;
					p2 c22 = c2 + rr * dy;
					if((c22 - A).abs() + (c22 - B).abs() < k) {
						c2 = c22;
					}
				}
				db rate = (c1 - o).abs() / ((c2 - o).abs());
				circle circ = {p2{0, 0}, (c2 - o).abs()};
				auto get = [&](p2 x) {
					x = x - o;
					p2 z;
					z.x = x % dx / rate;
					z.y = x % dy;
					return z;
				};
				std::vector<p2> P(t.size());
				for(int i = 0;i < (int) P.size();++i) {
					P[i] = t[i] & t[(i + 1) % t.size()];
				}
				for(int i = 0;i < (int) P.size();++i) {
					p2 x = P[i], y = P[(i + 1) % t.size()];
					x = get(x);
					y = get(y);
					ans += intersect(circ, x, y) * rate;
				}
			}
		}
	}
	printf("%.20lf\n", ans / 2);
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4284kb

input:

5 75
0 0
170 0
140 30
60 30
0 70

output:

7881.13325226654160360340

result:

ok found '7881.1332523', expected '7881.1332523', error '0.0000000'

Test #2:

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

input:

5 40
0 0
170 0
140 30
60 30
0 100

output:

0.00000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

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

input:

5 30000
0 0
1 2
1 5
0 2
0 1

output:

706960618.42809915542602539062

result:

ok found '706960618.4280992', expected '706960618.4280993', error '0.0000000'

Test #4:

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

input:

5 101
0 0
170 0
140 30
60 30
0 100

output:

18147.51756339364510495216

result:

ok found '18147.5175634', expected '18147.5175634', error '0.0000000'

Test #5:

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

input:

5 4
0 0
1 2
1 5
0 2
0 1

output:

22.87123588177685462597

result:

ok found '22.8712359', expected '22.8712359', error '0.0000000'

Test #6:

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

input:

2 1
0 0
1 1

output:

0.00000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

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

input:

2 2
0 0
1 1

output:

2.22144146907918127454

result:

ok found '2.2214415', expected '2.2214415', error '0.0000000'

Test #8:

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

input:

2 30000
-10000 10000
10000 -10000

output:

235619449.01923429965972900391

result:

ok found '235619449.0192343', expected '235619449.0192345', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2956ms
memory: 4360kb

input:

1982 30000
-2352 -9719
-2336 -9723
-2233 -9748
-2030 -9792
-2005 -9797
-2000 -9798
-1923 -9813
-1827 -9832
-1630 -9866
-1599 -9871
-1479 -9890
-1468 -9892
-1397 -9902
-1250 -9922
-1424 -9898
-1199 -9928
-950 -9955
-882 -9961
-832 -9965
-837 -9965
-805 -9968
-789 -9969
-808 -9967
-750 -9972
-747 -997...

output:

1963452789.21146321296691894531

result:

ok found '1963452789.2114632', expected '1963452789.2114513', error '0.0000000'

Test #10:

score: 0
Accepted
time: 3237ms
memory: 4264kb

input:

2000 30000
-9971 -8103
-9974 -7669
-9979 -8429
-9980 -8596
-9967 -6301
-9975 -6339
-9974 -5348
-9978 -4930
-9980 -5634
-9980 -5589
-9987 -5997
-9984 -5767
-9984 -5190
-9980 -5139
-9978 -4211
-9979 -4169
-9971 -2544
-9967 -2727
-9969 -2352
-9962 -1860
-9957 -579
-9963 -1432
-9962 -968
-9962 -674
-996...

output:

2302847929.37508869171142578125

result:

ok found '2302847929.3750887', expected '2302847929.3750844', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3153ms
memory: 4392kb

input:

2000 43
-2695 -9629
8195 5729
-9938 -1108
-9586 -2847
-9738 2271
8903 -4553
-2032 9791
-9923 1238
7294 6840
-9860 1663
3241 9459
-5277 -8493
-9646 -2633
-4653 8851
-257 9996
-387 -9992
-431 9990
-7092 7049
9357 3526
7863 -6177
5891 -8079
-7891 -6141
-1149 9933
-9619 2731
653 -9978
-2385 -9711
-2102 ...

output:

1118473.50734386756084859371

result:

ok found '1118473.5073439', expected '1118473.5073439', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2908ms
memory: 4268kb

input:

2000 1000
-9998 -199
-6845 -7289
-8682 4961
-9442 3292
-9818 -1896
-8354 5495
5289 8486
1711 9852
5776 -8162
4571 -8893
-249 -9996
3805 -9247
-7979 6027
-9834 -1812
9895 1444
-9367 3499
-616 -9980
7589 6511
5186 -8549
9452 3263
9998 -167
9425 3339
4621 8868
9999 128
9852 -1709
-36 9999
7816 6236
-55...

output:

62718830.47750905901193618774

result:

ok found '62718830.4775091', expected '62718830.4775094', error '0.0000000'

Test #13:

score: 0
Accepted
time: 2947ms
memory: 4376kb

input:

2000 5007
-9413 -3375
9379 3467
-9723 -2334
4422 8969
429 9990
-8665 4990
9649 -2622
-2849 -9585
9178 3968
-9127 -4085
-6548 -7557
-9078 -4193
7326 6806
8394 -5435
9995 -314
-1123 -9936
-6061 -7953
4007 9161
1869 -9823
7736 -6335
-3698 -9290
-7445 -6675
6589 -7522
-6779 7350
9552 2958
2878 -9576
-24...

output:

314563099.80548959970474243164

result:

ok found '314563099.8054896', expected '314563099.8054886', error '0.0000000'

Test #14:

score: 0
Accepted
time: 2956ms
memory: 4460kb

input:

2000 9909
-8481 -5297
1607 -9869
-9017 4322
99 9999
7923 -6100
327 -9994
-7678 -6405
8277 5610
-4849 8745
9450 -3267
-5397 8417
-9999 -135
-9999 114
9633 -2683
4529 -8915
3547 -9349
3587 9334
7849 6195
-9957 920
-4897 -8718
-2880 9576
-9115 -4112
-5067 8620
-4321 -9018
184 9998
5751 8180
86 9999
809...

output:

622562129.83782672882080078125

result:

ok found '622562129.8378267', expected '622562129.8378246', error '0.0000000'

Test #15:

score: 0
Accepted
time: 2974ms
memory: 4440kb

input:

2000 10001
-9701 2424
5769 8167
6540 7564
-9502 -3115
-9992 399
-1243 9922
3450 9385
-4982 8670
-9274 -3739
2691 -9630
-9959 894
-606 -9981
-8090 5877
9999 -34
2126 -9771
-8672 4978
-8374 5465
3424 9395
-3361 -9418
-9111 -4120
-4226 9062
9257 3780
8454 5341
4260 -9046
-8931 4497
-9816 1907
-4175 -90...

output:

706839355.67128133773803710938

result:

ok found '706839355.6712813', expected '706839355.6712799', error '0.0000000'

Test #16:

score: 0
Accepted
time: 2963ms
memory: 4448kb

input:

2000 10106
-78 9999
-2862 -9581
9965 827
9261 3771
-4809 8767
-9789 -2039
97 9999
8761 -4821
-2243 9745
836 9964
-598 9982
9940 1091
7987 -6017
-6487 -7609
-9200 -3917
-9707 2402
8605 -5093
1685 -9856
-406 9991
-5236 -8519
-1854 9826
-2039 9789
9085 -4177
-532 -9985
776 -9969
-209 9997
7024 -7117
-1...

output:

711795947.66243827342987060547

result:

ok found '711795947.6624383', expected '711795947.6624339', error '0.0000000'

Test #17:

score: 0
Accepted
time: 3116ms
memory: 4444kb

input:

2000 30000
-243 -9997
-6233 -7819
-8785 4777
1422 9898
9979 -645
5567 -8306
1676 -9858
-8679 4967
9947 -1027
-2643 9644
4383 8987
-5826 -8127
-2309 9729
-9116 -4109
7867 6173
9357 3525
3887 -9213
-8025 -5965
1930 -9811
-9275 -3735
9994 327
-9831 -1825
-3950 9186
-229 9997
-4634 -8861
-5735 -8191
414...

output:

1963404849.89914608001708984375

result:

ok found '1963404849.8991461', expected '1963404849.8991411', error '0.0000000'

Test #18:

score: 0
Accepted
time: 3659ms
memory: 4484kb

input:

2000 1000
8891 8891
6955 6955
4920 4920
-4006 -4006
-5341 -5341
-9888 -9888
-9028 -9028
-7032 -7032
-115 -115
3247 3247
-5885 -5885
-6716 -6716
-1992 -1992
865 865
-6939 -6939
-461 -461
-5705 -5705
-7859 -7859
5401 5401
-5787 -5787
-1791 -1791
-9180 -9180
8901 8901
2374 2374
-9585 -9585
4684 4684
-6...

output:

29024838.67855596169829368591

result:

ok found '29024838.6785560', expected '29024838.6785562', error '0.0000000'

Test #19:

score: 0
Accepted
time: 3763ms
memory: 4444kb

input:

2000 10000
5498 5498
2338 2338
-7237 -7237
-4384 -4384
2337 2337
-5016 -5016
5752 5752
-6674 -6674
2008 2008
9623 9623
1509 1509
6905 6905
-5705 -5705
-1389 -1389
-3881 -3881
4521 4521
3037 3037
9056 9056
3320 3320
-6374 -6374
874 874
5713 5713
-9651 -9651
-3633 -3633
7335 7335
-1143 -1143
7652 7652...

output:

360801547.03447347879409790039

result:

ok found '360801547.0344735', expected '360801547.0344678', error '0.0000000'

Test #20:

score: 0
Accepted
time: 3759ms
memory: 4396kb

input:

2000 15000
-9624 -9624
8301 8301
658 658
7304 7304
6640 6640
-2186 -2186
-481 -481
4953 4953
-8017 -8017
9522 9522
-4614 -4614
-4396 -4396
4236 4236
-4151 -4151
-4505 -4505
2911 2911
4839 4839
-1971 -1971
2636 2636
5379 5379
-5523 -5523
-2430 -2430
-715 -715
9063 9063
-3791 -3791
655 655
-3966 -3966...

output:

666125609.51144397258758544922

result:

ok found '666125609.5114440', expected '666125609.5114413', error '0.0000000'

Test #21:

score: 0
Accepted
time: 3661ms
memory: 4476kb

input:

2000 20000
7893 7893
47 47
4934 4934
-8512 -8512
2709 2709
7948 7948
6471 6471
5646 5646
-6086 -6086
-5469 -5469
3581 3581
-6782 -6782
6259 6259
7366 7366
6534 6534
-4861 -4861
-3491 -3491
-9201 -9201
-2845 -2845
1563 1563
-6070 -6070
-7882 -7882
8388 8388
8062 8062
-4559 -4559
88 88
8539 8539
-5210...

output:

1051229066.44322597980499267578

result:

ok found '1051229066.4432260', expected '1051229066.4432192', error '0.0000000'

Test #22:

score: 0
Accepted
time: 3636ms
memory: 4420kb

input:

2000 30000
-559 -559
-2871 -2871
-7318 -7318
7054 7054
-9824 -9824
-2649 -2649
-186 -186
2690 2690
-8603 -8603
7658 7658
-9898 -9898
2157 2157
331 331
1434 1434
5545 5545
9048 9048
5417 5417
9655 9655
2199 2199
-1016 -1016
-2990 -2990
-555 -555
-8419 -8419
6892 6892
-2109 -2109
-4055 -4055
-2837 -28...

output:

1837047515.11580777168273925781

result:

ok found '1837047515.1158078', expected '1837047515.1157992', error '0.0000000'

Test #23:

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

input:

3 109
0 0
100 0
0 100

output:

7178.76574068680383788887

result:

ok found '7178.7657407', expected '7178.7657407', error '0.0000000'

Test #24:

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

input:

3 150
200 0
100 100
0 0

output:

11542.29391720865896786563

result:

ok found '11542.2939172', expected '11542.2939172', error '0.0000000'

Test #25:

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

input:

3 59
50 50
100 50
100 100

output:

2691.49829797754500759766

result:

ok found '2691.4982980', expected '2691.4982980', error '0.0000000'

Test #26:

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

input:

3 6
3 0
0 4
0 0

output:

36.67738653413471894282

result:

ok found '36.6773865', expected '36.6773865', error '0.0000000'

Test #27:

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

input:

3 11833
10000 10000
-10000 10000
10000 9999

output:

109971363.26701547205448150635

result:

ok found '109971363.2670155', expected '109971363.2670155', error '0.0000000'

Test #28:

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

input:

3 11851
10000 10000
-10000 10000
10000 9900

output:

110302261.26082733273506164551

result:

ok found '110302261.2608273', expected '110302261.2608273', error '0.0000000'

Test #29:

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

input:

3 2594
10000 10000
9999 10000
10000 -10000

output:

5284815.04350353125482797623

result:

ok found '5284815.0435035', expected '5284815.0435035', error '0.0000000'

Test #30:

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

input:

3 201
0 0
200 0
100 173

output:

9982.29780365193073521368

result:

ok found '9982.2978037', expected '9982.2978037', error '0.0000000'

Test #31:

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

input:

3 104
0 0
200 0
100 1

output:

4642.75940810452630103100

result:

ok found '4642.7594081', expected '4642.7594081', error '0.0000000'

Test #32:

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

input:

3 5785
-10000 -10000
10000 9999
9999 10000

output:

26284310.86544757336378097534

result:

ok found '26284310.8654476', expected '26284310.8654476', error '0.0000000'

Test #33:

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

input:

4 13
10 10
20 10
20 20
10 20

output:

258.90940109964265047893

result:

ok found '258.9094011', expected '258.9094011', error '0.0000000'

Test #34:

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

input:

4 23724
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

807728367.96190559864044189453

result:

ok found '807728367.9619056', expected '807728367.9619061', error '0.0000000'

Test #35:

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

input:

4 143
100 0
200 100
100 200
0 100

output:

9482.92642485072428826243

result:

ok found '9482.9264249', expected '9482.9264249', error '0.0000000'

Test #36:

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

input:

4 109
0 1
100 0
101 100
1 101

output:

13860.58929386399722716305

result:

ok found '13860.5892939', expected '13860.5892939', error '0.0000000'

Test #37:

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

input:

4 52
0 0
100 0
100 50
0 50

output:

1166.64387253686936674058

result:

ok found '1166.6438725', expected '1166.6438725', error '0.0000000'

Test #38:

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

input:

4 52
0 0
50 0
50 100
0 100

output:

1166.64387253686959411425

result:

ok found '1166.6438725', expected '1166.6438725', error '0.0000000'

Test #39:

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

input:

4 35
0 10
10 0
100 90
90 100

output:

1760.15070562990490543598

result:

ok found '1760.1507056', expected '1760.1507056', error '0.0000000'

Test #40:

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

input:

8 309
0 100
100 0
250 0
350 100
350 250
250 350
100 350
0 250

output:

288293.52500220324145630002

result:

ok found '288293.5250022', expected '288293.5250022', error '0.0000000'

Test #41:

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

input:

6 65
0 50
10 0
70 0
80 10
70 50
50 80

output:

9724.72551383061181695666

result:

ok found '9724.7255138', expected '9724.7255138', error '0.0000000'

Test #42:

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

input:

4 36
0 100
0 0
100 0
20 20

output:

629.69931429069015393907

result:

ok found '629.6993143', expected '629.6993143', error '0.0000000'

Test #43:

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

input:

4 102
0 100
55 55
100 0
100 100

output:

13882.56131286994423135184

result:

ok found '13882.5613129', expected '13882.5613129', error '0.0000000'

Test #44:

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

input:

8 92
0 0
100 0
100 20
40 20
40 40
100 40
100 60
0 60

output:

19558.17811953465934493579

result:

ok found '19558.1781195', expected '19558.1781195', error '0.0000000'

Test #45:

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

input:

12 46
0 0
90 0
90 30
40 30
40 40
90 40
90 50
0 50
0 20
50 20
50 10
0 10

output:

8259.81383618299332738388

result:

ok found '8259.8138362', expected '8259.8138362', error '0.0000000'

Test #46:

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

input:

12 129
0 0
100 0
100 100
10 100
10 110
200 110
200 60
101 60
101 40
210 40
210 120
0 120

output:

57423.87010236619971692562

result:

ok found '57423.8701024', expected '57423.8701024', error '0.0000000'

Test #47:

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

input:

10 19
1000 0
1100 0
1200 100
1220 200
1200 110
1100 10
1000 10
900 110
880 200
900 100

output:

964.32566919843270625279

result:

ok found '964.3256692', expected '964.3256692', error '0.0000000'

Test #48:

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

input:

16 21
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10

output:

2810.53181389606925222324

result:

ok found '2810.5318139', expected '2810.5318139', error '0.0000000'

Test #49:

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

input:

8 25
0 1
100 0
5 5
200 5
105 0
205 1
205 10
0 10

output:

1689.50428910751338662521

result:

ok found '1689.5042891', expected '1689.5042891', error '0.0000000'

Test #50:

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

input:

8 65
0 1
50 0
5 5
200 5
150 0
205 1
205 10
0 10

output:

9196.67996498460161092225

result:

ok found '9196.6799650', expected '9196.6799650', error '0.0000000'

Test #51:

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

input:

9 73
99 100
100 100
99 99
301 99
300 100
301 100
201 274
200 273
199 274

output:

12766.67109971639547438826

result:

ok found '12766.6710997', expected '12766.6710997', error '0.0000000'

Test #52:

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

input:

15 36
0 0
10 0
20 0
30 0
40 0
50 0
40 10
30 20
20 30
10 40
0 50
0 40
0 30
0 20
0 10

output:

4740.00804595894624071661

result:

ok found '4740.0080460', expected '4740.0080460', error '0.0000000'

Test #53:

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

input:

11 12
0 0
100 0
90 5
80 10
70 15
60 20
50 25
40 20
30 15
20 10
10 5

output:

402.67553225698497953999

result:

ok found '402.6755323', expected '402.6755323', error '0.0000000'

Test #54:

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

input:

8 28
0 0
20 30
0 60
0 50
0 40
0 30
0 20
0 10

output:

2051.43325367636771261459

result:

ok found '2051.4332537', expected '2051.4332537', error '0.0000000'

Test #55:

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

input:

18 57
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 30
120 60
120 90
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

21479.62628450142437941395

result:

ok found '21479.6262845', expected '21479.6262845', error '0.0000000'

Test #56:

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

input:

15 69
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

22668.01221760982298292220

result:

ok found '22668.0122176', expected '22668.0122176', error '0.0000000'

Test #57:

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

input:

11 55
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120

output:

11579.13810640702649834566

result:

ok found '11579.1381064', expected '11579.1381064', error '0.0000000'

Test #58:

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

input:

9 29
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
0 120

output:

2397.29422740240215716767

result:

ok found '2397.2942274', expected '2397.2942274', error '0.0000000'

Test #59:

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

input:

29 14
0 0
100 0
100 50
0 50
0 20
80 20
80 30
10 30
10 40
20 40
30 40
40 40
50 40
60 40
70 40
80 40
90 40
90 30
90 20
90 10
80 10
70 10
60 10
50 10
40 10
30 10
20 10
10 10
0 10

output:

2203.79222231341373117175

result:

ok found '2203.7922223', expected '2203.7922223', error '0.0000000'

Test #60:

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

input:

24 171
0 0
100 0
100 100
200 100
200 0
300 0
300 100
300 200
200 200
200 300
300 300
300 400
300 500
200 500
200 400
100 400
100 500
0 500
0 400
0 300
100 300
100 200
0 200
0 100

output:

261180.68755668180529028177

result:

ok found '261180.6875567', expected '261180.6875567', error '0.0000000'

Test #61:

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

input:

4 62
50 50
100 50
100 101
50 100

output:

5737.57158769638954254333

result:

ok found '5737.5715877', expected '5737.5715877', error '0.0000000'

Test #62:

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

input:

10 163
100 300
150 50
100 0
200 50
250 150
250 50
400 0
300 50
350 50
400 300

output:

64397.21984701840847264975

result:

ok found '64397.2198470', expected '64397.2198470', error '0.0000000'

Test #63:

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

input:

10 110
300 400
50 350
50 300
0 400
50 250
150 250
50 200
0 100
50 150
300 100

output:

33550.69049144980090204626

result:

ok found '33550.6904914', expected '33550.6904914', error '0.0000000'

Test #64:

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

input:

5 147
0 0
100 100
60 40
200 200
40 60

output:

30148.18565571248109336011

result:

ok found '30148.1856557', expected '30148.1856557', error '0.0000000'

Test #65:

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

input:

5 93
0 0
100 100
60 40
120 120
40 60

output:

15528.96142370074812788516

result:

ok found '15528.9614237', expected '15528.9614237', error '0.0000000'

Test #66:

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

input:

5 13
0 0
100 100
51 49
200 200
49 51

output:

129.55261145313698989412

result:

ok found '129.5526115', expected '129.5526115', error '0.0000000'

Test #67:

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

input:

5 79
100 10
300 0
200 10
400 10
300 20

output:

4741.98936651002986764070

result:

ok found '4741.9893665', expected '4741.9893665', error '0.0000000'

Test #68:

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

input:

5 121
20 300
10 400
10 200
0 300
10 100

output:

23546.30580607100273482502

result:

ok found '23546.3058061', expected '23546.3058061', error '0.0000000'

Test #69:

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

input:

10 45
110 171
57 121
56 102
7 17
101 24
65 34
70 43
157 6
134 20
93 54

output:

6086.95352060319055453874

result:

ok found '6086.9535206', expected '6086.9535206', error '0.0000000'

Test #70:

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

input:

28 40
90 55
160 20
323 47
418 138
371 386
367 225
321 305
306 115
284 436
281 216
233 86
231 227
219 312
216 405
213 45
184 92
182 345
168 462
155 275
136 107
106 211
100 159
94 308
85 232
62 413
43 160
0 338
16 95

output:

841.80615108124118250998

result:

ok found '841.8061511', expected '841.8061511', error '0.0000000'

Test #71:

score: 0
Accepted
time: 6ms
memory: 4320kb

input:

100 5101
10000 0
9980 627
9921 1253
9822 1873
9685 2486
9510 3090
9297 3681
9048 4257
8763 4817
8443 5358
8090 5877
7705 6374
7289 6845
6845 7289
6374 7705
5877 8090
5358 8443
4817 8763
4257 9048
3681 9297
3090 9510
2486 9685
1873 9822
1253 9921
627 9980
0 10000
-627 9980
-1253 9921
-1873 9822
-2486...

output:

317036769.68810248374938964844

result:

ok found '317036769.6881025', expected '317036769.6881022', error '0.0000000'

Test #72:

score: 0
Accepted
time: 139ms
memory: 4340kb

input:

500 5245
10000 0
9999 125
9996 251
9992 376
9987 502
9980 627
9971 753
9961 878
9949 1003
9936 1128
9921 1253
9904 1377
9886 1502
9866 1626
9845 1750
9822 1873
9798 1997
9772 2120
9745 2242
9716 2364
9685 2486
9653 2608
9620 2729
9585 2850
9548 2970
9510 3090
9470 3209
9429 3328
9387 3446
9343 3564
...

output:

329398168.55282235145568847656

result:

ok found '329398168.5528224', expected '329398168.5528243', error '0.0000000'

Test #73:

score: 0
Accepted
time: 611ms
memory: 4352kb

input:

1000 11977
10000 0
9999 62
9999 125
9998 188
9996 251
9995 314
9992 376
9990 439
9987 502
9984 565
9980 627
9976 690
9971 753
9966 815
9961 878
9955 941
9949 1003
9943 1066
9936 1128
9928 1190
9921 1253
9913 1315
9904 1377
9895 1440
9886 1502
9876 1564
9866 1626
9856 1688
9845 1750
9834 1812
9822 18...

output:

752475152.98691999912261962891

result:

ok found '752475152.9869200', expected '752475152.9869199', error '0.0000000'

Test #74:

score: 0
Accepted
time: 9ms
memory: 4224kb

input:

100 3513
5675 0
5096 320
9219 1164
6323 1206
5537 1421
7180 2332
8787 3479
8780 4131
6560 3606
6417 4072
7534 5474
7349 6079
5101 4790
5742 6115
4154 5021
4618 6356
3825 6027
2789 5073
3987 8472
2099 5301
2014 6198
1762 6862
1775 9307
858 6793
397 6323
0 6011
-498 7921
-654 5183
-1292 6776
-1406 547...

output:

291600436.08686178922653198242

result:

ok found '291600436.0868618', expected '291600436.0868618', error '0.0000000'

Test #75:

score: 0
Accepted
time: 205ms
memory: 4336kb

input:

500 813
9861 0
6812 85
7520 189
7380 278
5178 260
7253 456
6724 507
7648 674
6898 695
5518 626
5005 632
9331 1298
4943 751
9438 1555
6461 1148
9637 1838
5312 1082
9406 2040
8241 1896
8053 1960
8715 2237
6398 1728
5037 1429
4855 1443
7371 2293
7768 2524
8513 2884
9057 3196
6740 2474
8789 3352
5730 22...

output:

116324442.33226534724235534668

result:

ok found '116324442.3322653', expected '116324442.3322655', error '0.0000000'

Test #76:

score: 0
Accepted
time: 821ms
memory: 4332kb

input:

1000 1934
8091 0
9198 57
9060 113
5747 108
5479 137
6865 215
9352 352
7129 313
5012 252
5016 283
7401 465
8909 616
9970 753
9436 772
7619 671
5368 507
6896 695
8556 917
6143 697
6802 816
9764 1233
9025 1197
8619 1199
5442 792
8519 1294
8530 1351
8292 1366
8711 1492
9103 1618
8293 1528
6769 1291
9047...

output:

293082740.83898133039474487305

result:

ok found '293082740.8389813', expected '293082740.8389802', error '0.0000000'

Test #77:

score: 0
Accepted
time: 9ms
memory: 4228kb

input:

100 3543
0 0
10000 0
10000 10000
9896 9853
9793 951
9690 1642
9587 4776
9484 6666
9381 5058
9278 8146
9175 6491
9072 714
8969 1675
8865 79
8762 3597
8659 4040
8556 1707
8453 8735
8350 6676
8247 8796
8144 2579
8041 2431
7938 3240
7835 827
7731 353
7628 5638
7525 1960
7422 7770
7319 8599
7216 5076
711...

output:

153098414.02573451399803161621

result:

ok found '153098414.0257345', expected '153098414.0257345', error '0.0000000'

Test #78:

score: 0
Accepted
time: 213ms
memory: 4324kb

input:

500 2217
0 0
10000 0
10000 10000
9979 4349
9959 5502
9939 255
9919 639
9899 5248
9879 974
9859 7593
9839 1091
9818 5905
9798 6216
9778 8699
9758 9951
9738 2044
9718 8181
9698 5522
9678 1888
9657 7549
9637 9475
9617 3347
9597 136
9577 775
9557 2467
9537 1000
9517 3873
9496 1460
9476 4350
9456 7880
94...

output:

136330637.39809250831604003906

result:

ok found '136330637.3980925', expected '136330637.3980920', error '0.0000000'

Test #79:

score: 0
Accepted
time: 853ms
memory: 4356kb

input:

1000 867
0 0
10000 0
10000 10000
9989 4685
9979 9134
9969 1180
9959 3397
9949 6194
9939 3697
9929 7962
9919 1358
9909 5778
9899 6522
9889 6286
9879 2382
9869 41
9859 3865
9849 997
9839 1746
9829 8380
9819 8211
9809 6070
9799 5539
9789 7476
9779 4391
9769 4092
9759 9264
9749 2333
9739 3849
9729 6011
...

output:

107766545.05328235030174255371

result:

ok found '107766545.0532824', expected '107766545.0532821', error '0.0000000'

Test #80:

score: 0
Accepted
time: 6ms
memory: 4336kb

input:

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

output:

102310941.97964861989021301270

result:

ok found '102310941.9796486', expected '102310941.9796486', error '0.0000000'

Test #81:

score: 0
Accepted
time: 131ms
memory: 4272kb

input:

500 3991
-125 0
-124 0
-123 0
-122 0
-121 0
-120 0
-119 0
-118 0
-117 0
-116 0
-115 0
-114 0
-113 0
-112 0
-111 0
-110 0
-109 0
-108 0
-107 0
-106 0
-105 0
-104 0
-103 0
-102 0
-101 0
-100 0
-99 0
-98 0
-97 0
-96 0
-95 0
-94 0
-93 0
-92 0
-91 0
-90 0
-89 0
-88 0
-87 0
-86 0
-85 0
-84 0
-83 0
-82 0
-...

output:

40481179.93895607441663742065

result:

ok found '40481179.9389561', expected '40481179.9389558', error '0.0000000'

Test #82:

score: 0
Accepted
time: 639ms
memory: 4380kb

input:

1000 3490
-250 0
-249 0
-248 0
-247 0
-246 0
-245 0
-244 0
-243 0
-242 0
-241 0
-240 0
-239 0
-238 0
-237 0
-236 0
-235 0
-234 0
-233 0
-232 0
-231 0
-230 0
-229 0
-228 0
-227 0
-226 0
-225 0
-224 0
-223 0
-222 0
-221 0
-220 0
-219 0
-218 0
-217 0
-216 0
-215 0
-214 0
-213 0
-212 0
-211 0
-210 0
-20...

output:

33897196.08429061621427536011

result:

ok found '33897196.0842906', expected '33897196.0842904', error '0.0000000'

Test #83:

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

input:

4 1431
0 0
2000 0
1500 866
500 866

output:

2901295.41157098021358251572

result:

ok found '2901295.4115710', expected '2901295.4115710', error '0.0000000'

Test #84:

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

input:

4 1494
0 0
2000 0
1500 867
500 867

output:

3204485.26207072753459215164

result:

ok found '3204485.2620707', expected '3204485.2620707', error '0.0000000'

Test #85:

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

input:

4 1354
0 0
1000 0
1500 866
1000 1732

output:

2526161.34907216858118772507

result:

ok found '2526161.3490722', expected '2526161.3490722', error '0.0000000'

Test #86:

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

input:

4 1543
0 0
1000 0
1500 867
1000 1733

output:

3441791.10439160186797380447

result:

ok found '3441791.1043916', expected '3441791.1043916', error '0.0000000'

Test #87:

score: 0
Accepted
time: 2293ms
memory: 4172kb

input:

2000 26184
-10000 9938
-10000 9914
-10000 9873
-10000 9831
-10000 9739
-10000 9710
-10000 9608
-10000 9595
-10000 9537
-10000 9524
-10000 9485
-10000 9470
-10000 9450
-10000 9428
-10000 9410
-10000 9376
-10000 9373
-10000 9321
-10000 9271
-10000 9245
-10000 9200
-10000 9027
-10000 9002
-10000 8959
-...

output:

1985529341.16838240623474121094

result:

ok found '1985529341.1683824', expected '1985529341.1683798', error '0.0000000'

Test #88:

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

input:

4 17353
-10000 0
0 -10000
10000 0
0 10000

output:

447635977.90355759859085083008

result:

ok found '447635977.9035576', expected '447635977.9035583', error '0.0000000'

Test #89:

score: 0
Accepted
time: 2246ms
memory: 4324kb

input:

2000 6251
-93 9907
-98 9902
-100 9900
-101 9899
-123 9877
-180 9820
-192 9808
-196 9804
-197 9803
-238 9762
-253 9747
-268 9732
-282 9718
-290 9710
-294 9706
-334 9666
-428 9572
-466 9534
-474 9526
-477 9523
-486 9514
-504 9496
-534 9466
-536 9464
-573 9427
-605 9395
-612 9388
-614 9386
-622 9378
-6...

output:

345070870.60815668106079101562

result:

ok found '345070870.6081567', expected '345070870.6081530', error '0.0000000'

Test #90:

score: 0
Accepted
time: 133ms
memory: 4328kb

input:

500 1226
6426 -6946
6448 -6925
6471 -6903
6495 -6880
6520 -6856
6546 -6831
6573 -6805
6660 -6721
6691 -6691
6692 -6690
6722 -6659
6751 -6629
6779 -6600
6832 -6545
6881 -6494
6904 -6470
6947 -6425
6967 -6404
6986 -6384
7004 -6365
7021 -6347
7037 -6330
7052 -6314
7081 -6283
7122 -6239
7160 -6198
7172 ...

output:

19862863.53608962893486022949

result:

ok found '19862863.5360896', expected '19862863.5360896', error '0.0000000'

Test #91:

score: 0
Accepted
time: 1667ms
memory: 4416kb

input:

2000 4433
-4 -6500
-3 -7000
0 -8000
1 -8000
4 -7000
5 -6500
6 -6000
7 -5000
8 -3000
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
9 21
9 22
9 23
9 24
9 25
9 26
9 27
9 28
9 29
9 30
9 31
9 32
9 33
9 34
9 35
9 36
9 37
9 38
9 39
9 40
9 41
9 42
9 43
9 44
9...

output:

87873437.29961095750331878662

result:

ok found '87873437.2996110', expected '87873437.2996017', error '0.0000000'

Test #92:

score: 0
Accepted
time: 374ms
memory: 4432kb

input:

835 4479
-750 -9935
-731 -9937
-702 -9940
-692 -9941
-661 -9944
-640 -9946
-608 -9949
-597 -9950
-574 -9952
-562 -9953
-537 -9955
-524 -9956
-497 -9958
-483 -9959
-454 -9961
-439 -9962
-408 -9964
-392 -9965
-375 -9966
-357 -9967
-338 -9968
-318 -9969
-297 -9970
-275 -9971
-252 -9972
-228 -9973
-203 ...

output:

105230091.07427106797695159912

result:

ok found '105230091.0742711', expected '105230091.0742711', error '0.0000000'

Test #93:

score: 0
Accepted
time: 1977ms
memory: 4304kb

input:

2000 12946
-5967 6
-5959 6
-5940 6
-5912 6
-5882 6
-5881 6
-5879 6
-5871 6
-5849 6
-5829 6
-5817 6
-5810 6
-5804 6
-5799 6
-5794 6
-5793 6
-5770 6
-5759 6
-5752 6
-5707 6
-5705 6
-5686 6
-5670 6
-5651 6
-5633 6
-5627 6
-5622 6
-5618 6
-5609 6
-5601 6
-5575 6
-5571 6
-5528 6
-5527 6
-5501 6
-5487 6
-...

output:

299525764.16781276464462280273

result:

ok found '299525764.1678128', expected '299525764.1678017', error '0.0000000'

Test #94:

score: 0
Accepted
time: 301ms
memory: 4332kb

input:

1004 1020
1000 9
999 9
998 9
997 9
996 9
995 9
994 9
993 9
992 9
991 9
990 9
989 9
988 9
987 9
986 9
985 9
984 9
983 9
982 9
981 9
980 9
979 9
978 9
977 9
976 9
975 9
974 9
973 9
972 9
971 9
970 9
969 9
968 9
967 9
966 9
965 9
964 9
963 9
962 9
961 9
960 9
959 9
958 9
957 9
956 9
955 9
954 9
953 9
9...

output:

1997125.54936616960912942886

result:

ok found '1997125.5493662', expected '1997125.5493661', error '0.0000000'

Test #95:

score: 0
Accepted
time: 22ms
memory: 4384kb

input:

183 18
-3 -4
-2 -8
-2 -7
-1 -7
-1 -8
0 -12
0 -6
-1 -6
-1 -4
0 -5
0 0
-1 -3
-1 0
-2 -6
-2 -3
-3 -2
-2 -2
-3 -1
-2 -1
-2 0
-12 0
-12 -1
-13 0
-15 0
-13 -1
-14 -1
-16 0
-16 -3
-15 -1
-13 -3
-14 -3
-13 -4
-15 -3
-15 -2
-16 -4
-16 -8
-15 -6
-15 -4
-14 -4
-12 -5
-13 -5
-12 -6
-12 -8
-13 -7
-13 -8
-12 -9
-...

output:

1049.87551521235218388028

result:

ok found '1049.8755152', expected '1049.8755152', error '0.0000000'

Test #96:

score: 0
Accepted
time: 18ms
memory: 4236kb

input:

183 19
4 -3
8 -2
7 -2
7 -1
8 -1
12 0
6 0
6 -1
4 -1
5 0
0 0
3 -1
0 -1
6 -2
3 -2
2 -3
2 -2
1 -3
1 -2
0 -2
0 -12
1 -12
0 -13
0 -15
1 -13
1 -14
0 -16
3 -16
1 -15
3 -13
3 -14
4 -13
3 -15
2 -15
4 -16
8 -16
6 -15
4 -15
4 -14
5 -12
5 -13
6 -12
8 -12
7 -13
8 -13
9 -12
9 -13
7 -14
8 -14
8 -15
6 -14
6 -13
5 -1...

output:

1110.41766241008576798777

result:

ok found '1110.4176624', expected '1110.4176624', error '0.0000000'

Test #97:

score: 0
Accepted
time: 22ms
memory: 4316kb

input:

183 18
-4 3
-8 2
-7 2
-7 1
-8 1
-12 0
-6 0
-6 1
-4 1
-5 0
0 0
-3 1
0 1
-6 2
-3 2
-2 3
-2 2
-1 3
-1 2
0 2
0 12
-1 12
0 13
0 15
-1 13
-1 14
0 16
-3 16
-1 15
-3 13
-3 14
-4 13
-3 15
-2 15
-4 16
-8 16
-6 15
-4 15
-4 14
-5 12
-5 13
-6 12
-8 12
-7 13
-8 13
-9 12
-9 13
-7 14
-8 14
-8 15
-6 14
-6 13
-5 14
-...

output:

1049.87551521235241125396

result:

ok found '1049.8755152', expected '1049.8755152', error '0.0000000'

Test #98:

score: 0
Accepted
time: 22ms
memory: 4392kb

input:

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

output:

1049.87551521235241125396

result:

ok found '1049.8755152', expected '1049.8755152', error '0.0000000'

Test #99:

score: 0
Accepted
time: 24ms
memory: 4324kb

input:

195 18
-14 -11
-13 -11
-13 -10
-14 -9
-14 -7
-15 -10
-15 -8
-14 -6
-13 -7
-13 -9
-12 -11
-12 -12
-11 -12
-11 -13
-10 -12
-10 -13
-9 -14
-9 -12
-8 -14
-7 -15
-6 -15
-8 -13
-7 -13
-8 -12
-7 -11
-8 -10
-8 -9
-6 -12
-7 -12
-6 -13
-4 -14
-6 -14
-5 -15
-8 -16
-5 -16
-4 -15
-4 -16
0 -16
0 -15
-3 -15
-1 -14...

output:

1044.14827969501675397623

result:

ok found '1044.1482797', expected '1044.1482797', error '0.0000000'

Test #100:

score: 0
Accepted
time: 24ms
memory: 4244kb

input:

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

output:

1044.14827969501675397623

result:

ok found '1044.1482797', expected '1044.1482797', error '0.0000000'

Test #101:

score: 0
Accepted
time: 24ms
memory: 4324kb

input:

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

output:

1104.79387519974238784926

result:

ok found '1104.7938752', expected '1104.7938752', error '0.0000000'

Test #102:

score: 0
Accepted
time: 24ms
memory: 4248kb

input:

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

output:

1104.79387519974238784926

result:

ok found '1104.7938752', expected '1104.7938752', error '0.0000000'

Test #103:

score: 0
Accepted
time: 23ms
memory: 4316kb

input:

186 19
-13 -16
-12 -15
-12 -14
-13 -15
-15 -15
-15 -14
-14 -14
-13 -13
-14 -13
-14 -12
-13 -12
-12 -13
-13 -14
-11 -13
-9 -13
-8 -14
-11 -14
-11 -15
-12 -16
-6 -16
-10 -15
-7 -15
-5 -16
-2 -16
-5 -15
-6 -15
-7 -14
-6 -14
-4 -15
-3 -15
-4 -14
-4 -13
-2 -11
-1 -14
-1 -15
-2 -12
-2 -14
-3 -13
-3 -14
-1...

output:

1101.97638004236250708345

result:

ok found '1101.9763800', expected '1101.9763800', error '0.0000000'

Test #104:

score: 0
Accepted
time: 24ms
memory: 4140kb

input:

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

output:

1227.24752304722051121644

result:

ok found '1227.2475230', expected '1227.2475230', error '0.0000000'

Test #105:

score: 0
Accepted
time: 23ms
memory: 4228kb

input:

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

output:

1041.63131526153165395954

result:

ok found '1041.6313153', expected '1041.6313153', error '0.0000000'

Test #106:

score: 0
Accepted
time: 19ms
memory: 4288kb

input:

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

output:

1041.63131526153165395954

result:

ok found '1041.6313153', expected '1041.6313153', error '0.0000000'

Test #107:

score: 0
Accepted
time: 23ms
memory: 4324kb

input:

191 19
-2 -3
-2 -2
-1 -2
0 -1
-3 -2
-5 -4
-5 -3
-4 -2
-6 -2
-8 -4
-9 -4
-9 -5
-8 -5
-7 -4
-7 -6
-6 -5
-6 -3
-5 -5
-4 -4
-3 -4
-5 -6
-6 -6
-6 -7
-8 -9
-7 -9
-3 -5
-2 -5
-4 -7
-2 -6
-1 -6
-1 -7
-2 -7
-2 -8
-1 -10
-2 -9
-1 -11
-3 -9
-4 -10
-3 -10
-2 -11
-3 -11
-3 -12
-1 -12
-1 -13
-3 -13
-1 -14
-1 -15
...

output:

1114.90041686855374791776

result:

ok found '1114.9004169', expected '1114.9004169', error '0.0000000'

Test #108:

score: 0
Accepted
time: 24ms
memory: 4228kb

input:

191 18
3 -2
2 -2
2 -1
1 0
2 -3
4 -5
3 -5
2 -4
2 -6
4 -8
4 -9
5 -9
5 -8
4 -7
6 -7
5 -6
3 -6
5 -5
4 -4
4 -3
6 -5
6 -6
7 -6
9 -8
9 -7
5 -3
5 -2
7 -4
6 -2
6 -1
7 -1
7 -2
8 -2
10 -1
9 -2
11 -1
9 -3
10 -4
10 -3
11 -2
11 -3
12 -3
12 -1
13 -1
13 -3
14 -1
15 -1
14 -2
15 -3
15 -4
14 -3
13 -4
13 -6
14 -4
14 -5...

output:

1054.11175020956329717592

result:

ok found '1054.1117502', expected '1054.1117502', error '0.0000000'

Test #109:

score: 0
Accepted
time: 24ms
memory: 4324kb

input:

191 18
-3 2
-2 2
-2 1
-1 0
-2 3
-4 5
-3 5
-2 4
-2 6
-4 8
-4 9
-5 9
-5 8
-4 7
-6 7
-5 6
-3 6
-5 5
-4 4
-4 3
-6 5
-6 6
-7 6
-9 8
-9 7
-5 3
-5 2
-7 4
-6 2
-6 1
-7 1
-7 2
-8 2
-10 1
-9 2
-11 1
-9 3
-10 4
-10 3
-11 2
-11 3
-12 3
-12 1
-13 1
-13 3
-14 1
-15 1
-14 2
-15 3
-15 4
-14 3
-13 4
-13 6
-14 4
-14 ...

output:

1054.11175020956329717592

result:

ok found '1054.1117502', expected '1054.1117502', error '0.0000000'

Test #110:

score: 0
Accepted
time: 24ms
memory: 4236kb

input:

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

output:

1054.11175020956329717592

result:

ok found '1054.1117502', expected '1054.1117502', error '0.0000000'

Test #111:

score: 0
Accepted
time: 1916ms
memory: 4344kb

input:

1759 65
19 19
20 21
20 20
21 21
21 20
22 20
23 19
24 17
24 18
25 18
25 17
27 18
29 18
30 19
30 22
29 20
26 20
29 19
28 19
26 18
24 19
27 19
24 20
23 20
21 22
23 22
23 21
24 21
25 20
25 21
26 21
25 22
24 22
25 23
25 24
24 23
20 23
22 24
20 24
22 25
19 25
19 27
21 28
22 29
24 29
23 28
24 28
25 29
24 3...

output:

12176.41578463465884851757

result:

ok found '12176.4157846', expected '12176.4157846', error '0.0000000'

Test #112:

score: 0
Accepted
time: 1807ms
memory: 4352kb

input:

1717 63
26 39
27 41
25 41
26 43
23 43
24 42
24 41
23 39
21 40
23 40
23 41
22 41
23 42
22 42
22 44
24 44
24 45
19 45
21 44
20 44
21 43
20 43
20 42
19 42
19 44
15 45
18 45
23 46
26 46
26 45
25 45
25 44
26 44
27 45
28 45
27 44
28 44
28 43
27 43
26 42
30 42
29 43
31 43
33 44
31 44
33 45
30 44
29 44
32 4...

output:

11820.46500319033475534525

result:

ok found '11820.4650032', expected '11820.4650032', error '0.0000000'

Test #113:

score: 0
Accepted
time: 6ms
memory: 4268kb

input:

83 303
0 164
1 197
1 150
0 163
0 65
1 100
1 41
0 64
0 25
1 40
1 2
0 24
0 10
1 1
0 9
0 0
2 0
2 59
1 101
1 149
2 60
2 165
1 216
1 238
2 166
2 470
1 462
1 535
2 471
2 771
1 651
1 714
2 772
2 861
1 831
1 900
2 862
2 907
1 901
1 911
2 908
2 957
1 912
1 983
2 958
2 999
0 999
0 997
1 998
1 987
0 996
0 993
...

output:

372903.19436624256195500493

result:

ok found '372903.1943662', expected '372903.1943662', error '0.0000000'

Test #114:

score: 0
Accepted
time: 7ms
memory: 4388kb

input:

97 428
522 0
474 1
543 1
523 0
670 0
544 1
652 1
671 0
736 0
653 1
668 1
737 0
758 0
723 1
752 1
759 0
831 0
753 1
804 1
832 0
875 0
805 1
845 1
876 0
915 0
846 1
957 1
916 0
981 0
975 1
985 1
982 0
986 0
986 1
992 1
987 0
999 0
998 1
999 1
999 2
997 1
993 1
998 2
969 2
974 1
958 1
968 2
813 2
722 1...

output:

571148.97499702183995395899

result:

ok found '571148.9749970', expected '571148.9749970', error '0.0000000'

Test #115:

score: 0
Accepted
time: 19ms
memory: 4396kb

input:

171 1000
3 40
2 61
2 48
1 53
1 56
2 62
2 71
1 57
1 67
2 102
2 72
3 41
3 146
2 161
2 193
3 147
3 165
2 194
2 219
1 257
1 298
2 220
2 249
3 166
3 196
2 299
2 250
1 380
1 413
2 426
2 300
3 197
3 304
2 427
2 529
3 305
3 547
2 565
2 530
1 414
1 453
2 566
2 572
1 454
1 586
2 662
2 573
3 548
3 707
2 663
2 ...

output:

1787797.08258535782806575298

result:

ok found '1787797.0825854', expected '1787797.0825854', error '0.0000000'

Test #116:

score: 0
Accepted
time: 21ms
memory: 4268kb

input:

169 1000
292 1
223 0
460 0
447 1
496 1
461 0
510 0
497 1
528 1
511 0
650 0
632 1
614 1
573 2
602 2
633 1
653 1
651 0
841 0
837 1
846 1
806 2
869 2
847 1
872 1
842 0
899 0
873 1
917 1
900 0
912 0
928 1
918 1
901 2
956 2
929 1
995 1
913 0
999 0
996 1
995 2
997 2
997 1
999 1
999 2
998 2
999 3
996 3
994...

output:

1787889.16569904121570289135

result:

ok found '1787889.1656990', expected '1787889.1656990', error '0.0000000'

Test #117:

score: 0
Accepted
time: 3533ms
memory: 4324kb

input:

2000 1161
3316 4595
4152 4662
4692 5559
4805 5785
4445 6103
3936 6224
4153 6375
4382 6574
4721 6189
6281 6497
5858 5760
6308 5713
6729 5979
6197 6721
6374 7103
6205 6871
5757 6512
5087 6488
5842 7042
4897 7761
5110 7282
4851 6381
4809 6715
4810 7013
4808 7440
3482 7551
3746 7800
3112 7468
3479 7039
...

output:

419757297.18455809354782104492

result:

ok found '419757297.1845581', expected '419757297.1845574', error '0.0000000'

Test #118:

score: 0
Accepted
time: 3323ms
memory: 4352kb

input:

2000 155
-2720 -1363
-2774 1491
-2754 1837
-2751 4697
-2756 8857
-2915 9905
-2524 9530
-2774 9694
-2604 8757
-2541 1908
-2608 1807
-2650 3360
-2663 8316
-2640 -7601
-2644 -5216
-2672 -7637
-2673 8295
-2680 3413
-2707 9287
-2682 -5749
-2678 -8779
-3156 -9988
861 -9952
1509 -9829
1199 -9503
1342 -8775...

output:

4021264.63402511551976203918

result:

ok found '4021264.6340251', expected '4021264.6340251', error '0.0000000'

Test #119:

score: 0
Accepted
time: 3329ms
memory: 4356kb

input:

1999 1266
389 180
389 168
363 119
380 137
375 139
451 124
404 140
453 147
541 133
492 206
483 188
499 256
572 138
571 199
608 165
573 25
554 45
546 72
502 54
520 83
539 130
459 83
437 103
454 57
428 60
439 77
420 74
421 83
422 108
418 106
396 124
406 82
418 59
372 88
356 52
363 35
402 46
422 52
420 ...

output:

6440404.45422141533344984055

result:

ok found '6440404.4542214', expected '6440404.4542214', error '0.0000000'

Test #120:

score: 0
Accepted
time: 3319ms
memory: 4356kb

input:

1998 4780
740 -650
753 -696
719 -663
683 -565
593 -539
586 -446
648 -415
713 -447
639 -331
566 -351
523 -297
575 -264
616 -286
541 -227
462 -324
460 -370
479 -380
585 -430
566 -427
510 -401
585 -516
489 -435
384 -380
423 -442
478 -536
379 -415
313 -361
325 -318
263 -421
303 -482
306 -512
287 -516
25...

output:

96030061.66710492968559265137

result:

ok found '96030061.6671049', expected '96030061.6671051', error '0.0000000'

Test #121:

score: 0
Accepted
time: 3242ms
memory: 4324kb

input:

2000 17184
8596 -48
7794 130
7241 379
7079 -51
6516 146
6126 523
5542 402
6080 -117
6102 -221
5556 -714
6301 -699
6527 -264
6588 -1964
6638 -1591
6787 -1210
6613 -2173
7031 -1363
7158 -615
7338 -1411
7520 -1518
7412 -797
7297 -575
8579 -546
8285 -1447
8873 -845
9229 -2075
9066 -1543
8703 -2732
8751 ...

output:

1299273363.62224841117858886719

result:

ok found '1299273363.6222484', expected '1299273363.6222489', error '0.0000000'

Test #122:

score: 0
Accepted
time: 2930ms
memory: 4432kb

input:

1982 2994
-2352 -9719
-2336 -9723
-2233 -9748
-2030 -9792
-2005 -9797
-2000 -9798
-1923 -9813
-1827 -9832
-1630 -9866
-1599 -9871
-1479 -9890
-1468 -9892
-1397 -9902
-1250 -9922
-1424 -9898
-1199 -9928
-950 -9955
-882 -9961
-832 -9965
-837 -9965
-805 -9968
-789 -9969
-808 -9967
-750 -9972
-747 -9972...

output:

281987464.99426966905593872070

result:

ok found '281987464.9942697', expected '281987464.9942697', error '0.0000000'

Test #123:

score: 0
Accepted
time: 3292ms
memory: 4276kb

input:

2000 24944
-9971 -8103
-9974 -7669
-9979 -8429
-9980 -8596
-9967 -6301
-9975 -6339
-9974 -5348
-9978 -4930
-9980 -5634
-9980 -5589
-9987 -5997
-9984 -5767
-9984 -5190
-9980 -5139
-9978 -4211
-9979 -4169
-9971 -2544
-9967 -2727
-9969 -2352
-9962 -1860
-9957 -579
-9963 -1432
-9962 -968
-9962 -674
-996...

output:

1882969072.34168457984924316406

result:

ok found '1882969072.3416846', expected '1882969072.3416920', error '0.0000000'