QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477606#8513. Insects, Mathematics, Accuracy, and Efficiencycrimson231AC ✓43ms4504kbC++209.7kb2024-07-14 07:03:262024-07-14 07:03:26

Judging History

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

  • [2024-07-14 07:03:26]
  • 评测
  • 测评结果:AC
  • 用时:43ms
  • 内存:4504kb
  • [2024-07-14 07:03:26]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <deque>
#include <cassert>
#include <cstring>
typedef long long ll;
//typedef long double ld;
typedef double ld;
typedef std::vector<ld> Vld;
const ld INF = 1e17;
const ld TOL = 1e-12;
const ld PI = acos(-1);
const int LEN = 1e4 + 5;
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
inline ll sq(int x) { return (ll)x * x; }
inline ld norm(ld th) {
	while (th < 0) th += 2 * PI;
	while (sign(th - 2 * PI) >= 0) th -= 2 * PI;
	return th;
}

int N, R;
ld memo[2000];
struct Info { int hi, lo; };
struct Pos {
	ld x, y;
	Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
	bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
	bool operator != (const Pos& p) const { return !zero(x - p.x) || !zero(y - p.y); }
	bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
	bool operator <= (const Pos& p) const { return *this < p || *this == p; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
	Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
	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 Pos& p) const { return { x * p.x, y * p.y }; }
	Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
	Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
	Pos& operator *= (const ld& scale) { x *= scale; y *= scale; return *this; }
	Pos& operator /= (const ld& scale) { x /= scale; y /= scale; return *this; }
	Pos operator - () const { return { -x, -y }; }
	Pos operator ~ () const { return { -y, x }; }
	Pos operator ! () const { return { y, x }; }
	ld xy() const { return x * y; }
	Pos rot(ld the) { return { x * cos(the) - y * sin(the), x * sin(the) + y * cos(the) }; }
	ld Euc() const { return x * x + y * y; }
	ld mag() const { return sqrt(Euc()); }
	Pos unit() const { return *this / mag(); }
	ld rad() const { return norm(atan2(y, x)); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
	bool close(const Pos& p) const { return zero((*this - p).Euc()); }
	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = { 0, 0 };
typedef std::vector<Pos> Polygon;
bool cmpx(const Pos& p, const Pos& q) { return p.x == q.x ? p.y < q.y : p.x < q.x; }
bool cmpy(const Pos& p, const Pos& q) { return p.y == q.y ? p.x < q.x : p.y < q.y; }
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 zero(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 ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && sign(ret) >= 0; }
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && sign(ret) > 0; }
int inner_check_bi_search(const std::vector<Pos>& H, const Pos& p) {//convex
	int sz = H.size();
	if (!sz) return -1;
	if (sz == 1) return p == H[0] ? 0 : -1;
	if (sz == 2) return on_seg_strong(H[0], H[1], p) ? 0 : -1;
	if (cross(H[0], H[1], p) < 0 || cross(H[0], H[sz - 1], p) > 0) return -1;
	if (on_seg_strong(H[0], H[1], p) || on_seg_strong(H[0], H[sz - 1], p)) return 0;
	int s = 0, e = sz - 1, m;
	while (s + 1 < e) {
		m = s + e >> 1;
		if (cross(H[0], H[m], p) > 0) s = m;
		else e = m;
	}
	if (cross(H[s], H[e], p) > 0) return 1;
	else if (on_seg_strong(H[s], H[e], p)) return 0;
	else return -1;
}
ld area(const std::vector<Pos>& H) {
	ld ret = 0;
	int sz = H.size();
	for (int i = 0; i < sz; i++) {
		Pos cur = H[i], nxt = H[(i + 1) % sz];
		ret += cross(O, cur, nxt);
	}
	return ret;
}
std::vector<Pos> graham_scan(std::vector<Pos>& C) {
	std::vector<Pos> H;
	if (C.size() < 3) {
		std::sort(C.begin(), C.end());
		return C;
	}
	std::swap(C[0], *min_element(C.begin(), C.end()));
	std::sort(C.begin() + 1, C.end(), [&](const Pos& p, const Pos& q) -> bool {
		int ret = ccw(C[0], p, q);
		if (!ret) return (C[0] - p).Euc() < (C[0] - q).Euc();
		return ret > 0;
		}
	);
	C.erase(unique(C.begin(), C.end()), C.end());
	int sz = C.size();
	for (int i = 0; i < sz; i++) {
		while (H.size() >= 2 && ccw(H[H.size() - 2], H.back(), C[i]) <= 0)
			H.pop_back();
		H.push_back(C[i]);
	}
	return H;
}
inline Vld circle_line_intersections(const Pos& s, const Pos& e, const ll& r) {
	//https://math.stackexchange.com/questions/311921/get-location-of-vector-circle-intersection
	Pos vec = e - s;
	Pos OM = s - O;
	ld a = vec.Euc();
	ld b = vec * OM;
	ld c = OM.Euc() - r * r;
	ld J = b * b - a * c;
	if (J < -TOL) return {};
	ld det = sqrt(std::max((ld)0, J));
	ld lo = (-b - det) / a;
	ld hi = (-b + det) / a;
	Vld ret;
	auto the = [&](ld rt) { return (s + (e - s) * rt).rad(); };
	ret.push_back(the(hi));
	if (zero(det)) return ret;
	ret.push_back(the(lo));
	return ret;
}
Info find_tangent_bi_search(const Polygon& H, const Pos& p) {
	if (inner_check_bi_search(H, p) >= 0) return { -1, -1 };
	int sz = H.size();
	int i1{ 0 }, i2{ 0 };
	int ccw1 = ccw(p, H[0], H[1]), ccwN = ccw(p, H[0], H[sz - 1]);
	if (ccw1 * ccwN >= 0) {
		i1 = 0;
		if (!ccw1 && dot(p, H[1], H[0]) > 0) i1 = 1;
		if (!ccwN && dot(p, H[sz - 1], H[0]) > 0) i1 = sz - 1;
		int s = 0, e = sz - 1, m;
		if (!ccw1) s += 1;
		if (!ccwN) e -= 1;
		bool f = ccw(p, H[s], H[s + 1]) >= 0;
		while (s < e) {
			m = s + e >> 1;
			Pos p1 = p, cur = H[m], nxt = H[(m + 1) % sz];
			if (!f) std::swap(p1, cur);//normalize
			if (ccw(p1, cur, nxt) > 0) s = m + 1;
			else e = m;
		}
		i2 = s;
		if (on_seg_weak(p, H[i2], H[(i2 + 1) % sz])) i2 = (i2 + 1) % sz;
	}
	else {
		//divide hull
		int s = 0, e = sz - 1, k, m;
		bool f = ccw1 > 0 && ccwN < 0;//if H[k] is between H[0] && p
		while (s + 1 < e) {
			k = s + e >> 1;
			int CCW = ccw(H[0], H[k], p);
			if (!f) CCW *= -1;//normailze
			if (CCW > 0) s = k;
			else e = k;
		}

		//search lower hull
		int s1 = 0, e1 = s;
		while (s1 < e1) {
			m = s1 + e1 >> 1;
			Pos p1 = p, cur = H[m], nxt = H[(m + 1) % sz];
			if (!f) std::swap(p1, cur);//normalize
			if (ccw(p1, cur, nxt) > 0) s1 = m + 1;
			else e1 = m;
		}
		i1 = s1;
		if (on_seg_weak(p, H[i1], H[(i1 + 1) % sz])) i1 = (i1 + 1) % sz;

		//search upper hull
		int s2 = e, e2 = sz - 1;
		while (s2 < e2) {
			m = s2 + e2 >> 1;
			Pos p1 = p, cur = H[m], nxt = H[(m + 1) % sz];
			if (!f) std::swap(p1, cur);//normalize
			if (ccw(p1, cur, nxt) < 0) s2 = m + 1;
			else e2 = m;
		}
		i2 = s2;
		if (on_seg_weak(p, H[i2], H[(i2 + 1) % sz])) i2 = (i2 + 1) % sz;
	}
	if (ccw(p, H[i1], H[i2]) < 0) std::swap(i1, i2);//normalize
	return { i1, i2 };
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(10);
	std::cin >> N >> R;
	ll x, y;
	Polygon C;
	for (int i = 0; i < N; i++) {
		std::cin >> x >> y;
		//assert(R * R >= x * x + y * y);
		if (R * R < x * x + y * y) continue;
		C.push_back(Pos(x, y));
	}
	N = C.size();

	if (N == 1) { std::cout << 0 << "\n"; return; }
	if (N == 2) {
		Pos& p1 = C[0], & p2 = C[1];
		Pos vec = ~(p1 - p2).unit();
		Pos q1 = vec * R;
		Pos q2 = -vec * R;
		ld a = std::max(std::abs(cross(p1, p2, q1)), std::abs(cross(p1, p2, q2)));
		std::cout << a * .5 << "\n";
		return;
	}
	Polygon H = graham_scan(C);
	N = H.size();

	memset(memo, 0, sizeof memo);
	for (int i = 0; i < N; i++) memo[i + 1] = memo[i] + H[i] / H[(i + 1) % N];

	Vld arcs;
	for (int i = 0; i < N; i++) {
		Pos& s = H[i], & e = H[(i + 1) % N];
		auto inx = circle_line_intersections(s, e, R);
		for (ld& rd : inx) arcs.push_back(rd);
	}

	arcs.push_back(0);
	arcs.push_back(2 * PI);
	std::sort(arcs.begin(), arcs.end());

	ld ret = memo[N];
	int sz = arcs.size();
	for (int i = 0; i < sz - 1; i++) {
		ld& s = arcs[i], & e = arcs[i + 1];
		if (zero(s - e)) continue;
		ld m = (s + e) * .5;
		Pos S = Pos(1, 0).rot(s) * R;
		Pos E = Pos(1, 0).rot(e) * R;
		Pos M = Pos(1, 0).rot(m) * R;
		int lo = 0, hi = 0;
		ld dl = INF, dr = INF;
		for (int j = 0; j < N; j++) {
			if (ccw(M, H[lo], H[j]) > 0 || 
				(!ccw(M, H[lo], H[j]) && (M - H[j]).Euc() < dl)) {
				lo = j;
			}
			if (ccw(M, H[hi], H[j]) < 0 || 
				(!ccw(M, H[hi], H[j]) && (M - H[j]).Euc() < dr)) {
				hi = j;
			}
		}
		Pos& u = H[hi], & v = H[lo];
		Pos vec = ~(v - u).unit();
		Pos OP = vec * R;
		bool f = 0;
		if (ccw(O, S, OP) >= 0 && ccw(O, E, OP) <= 0) f = 1;
		ld a, a1, a2, a3 = 0;
		if (hi == lo) {
			a1 = a2 = a3 = memo[N];
		}
		else {
			a = 0;
			for (int j = hi; j != lo; j = (j + 1) % N) {
				a += cross(O, H[j], H[(j + 1) % N]);
			}
			a1 = a + cross(O, H[lo], S) + cross(O, S, H[hi]);
			a2 = a + cross(O, H[lo], E) + cross(O, E, H[hi]);
			if (f) a3 = a + cross(O, H[lo], OP) + cross(O, OP, H[hi]);
		}
		ret = std::max({ ret, a1, a2, a3 });
	}
	std::cout << ret * .5 << "\n";
	return;
}
int main() { solve(); return 0; }//boj31759 Insects, Mathematics, Accuracy, and Efficiency

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2000000.0000000000

result:

ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'

Test #2:

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

input:

2 100
17 7
19 90

output:

4849.7046444376

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

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

input:

1 100
13 37

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

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

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2240000.0000000000

result:

ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'

Test #5:

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

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.4249492380

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

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

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.5625617660

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

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

input:

4 1000
-600 700
-300 900
0 800
-800 400

output:

892213.5954999579

result:

ok found '892213.595499958', expected '892213.595499958', error '0.000000000'

Test #8:

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

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.4944640259

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314026591.7801103592

result:

ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'

Test #10:

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

input:

2 10000
-9999 0
-9998 -1

output:

12070.5678118655

result:

ok found '12070.567811865', expected '12070.567811865', error '0.000000000'

Test #11:

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

input:

1604 10000
2604 -9655
7380 -6748
9963 859
9843 1765
-1452 9894
-2024 9793
-8862 4633
-2604 -9655
9301 3673
9871 -1601
-565 -9984
9640 -2659
9312 3645
-8291 -5591
7879 6158
1301 9915
509 9987
7757 -6311
-9301 -3673
7702 -6378
5415 8407
-9971 761
9023 -4311
-6785 7346
-9852 1714
-9788 -2048
9819 -1894...

output:

314156571.1123499870

result:

ok found '314156571.112349987', expected '314156571.112349927', error '0.000000000'

Test #12:

score: 0
Accepted
time: 32ms
memory: 4424kb

input:

1444 10000
3378 8342
-734 8970
-3168 8424
1741 8830
-3631 8235
-6622 -6095
8605 -2637
-3762 8176
-8509 2932
-8915 1234
-1919 -8793
-7663 -4720
3040 -8471
-7357 5184
5746 -6927
5827 -6859
6519 6205
328 -8994
-5282 7287
4797 -7615
-5505 7120
-2733 8575
6902 5776
-4666 7696
6946 5723
-4154 7984
6644 60...

output:

257163269.6295304894

result:

ok found '257163269.629530489', expected '257163269.629530489', error '0.000000000'

Test #13:

score: 0
Accepted
time: 28ms
memory: 4424kb

input:

1396 10000
-5817 -5492
-692 -7970
-6967 -3932
-6316 -4910
-6562 4576
-7358 3140
2376 7639
-7883 1363
-2337 7651
-6950 -3962
-6927 4002
4961 -6276
5036 6216
7274 3330
-6976 3916
1490 7860
-2816 7488
-6927 -4002
-3107 7372
-6802 4211
4353 6712
-5594 -5719
875 -7952
-2943 7439
-4672 6494
-4405 -6678
-3...

output:

207875930.5000000000

result:

ok found '207875930.500000000', expected '207875930.500000000', error '0.000000000'

Test #14:

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

input:

1252 10000
-6409 2815
5515 4311
6506 2583
4459 5396
2493 6541
-3215 6218
2911 -6366
0 -7000
658 6969
312 -6993
-1100 -6913
6621 2272
-1081 -6916
-6901 1173
-658 6969
5227 -4656
2911 6366
6715 -1977
3812 5871
1015 -6926
6061 3502
-473 6984
5079 -4817
614 -6973
-2667 6472
1446 6849
-1791 -6767
-2004 -...

output:

164951741.6576544046

result:

ok found '164951741.657654405', expected '164951741.657654375', error '0.000000000'

Test #15:

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

input:

42 10000
-800 -8
-799 -40
-730 -247
-599 -399
-591 -406
-541 -443
-283 -562
-189 -584
-43 -600
223 -577
507 -464
575 -417
607 -391
654 -346
677 -320
775 -149
794 -74
726 251
718 264
698 292
689 304
619 380
538 443
331 546
315 551
279 562
237 573
182 584
116 593
52 598
-37 599
-57 598
-238 573
-314 5...

output:

8755559.4805068858

result:

ok found '8755559.480506886', expected '8755559.480506888', error '0.000000000'

Test #16:

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

input:

171 10000
-800 -29
-794 -79
-788 -108
-785 -120
-776 -149
-775 -152
-768 -171
-748 -215
-745 -221
-738 -234
-709 -280
-704 -287
-695 -299
-688 -308
-679 -319
-667 -333
-660 -341
-631 -370
-607 -392
-593 -404
-583 -412
-564 -427
-546 -440
-527 -453
-458 -493
-422 -511
-378 -530
-360 -537
-329 -548
-2...

output:

8773418.7784261331

result:

ok found '8773418.778426133', expected '8773418.778426135', error '0.000000000'

Test #17:

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

input:

202 10000
-900 -43
-898 -70
-895 -103
-894 -111
-890 -140
-888 -152
-873 -223
-868 -242
-862 -263
-856 -281
-835 -339
-826 -360
-812 -391
-805 -405
-793 -428
-788 -437
-780 -451
-768 -471
-757 -489
-743 -510
-731 -527
-707 -559
-692 -577
-673 -599
-664 -609
-652 -622
-621 -653
-607 -666
-596 -676
-5...

output:

10316038.3155667689

result:

ok found '10316038.315566769', expected '10316038.315566765', error '0.000000000'

Test #18:

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

input:

252 10000
-900 -43
-899 -60
-898 -73
-897 -84
-893 -120
-888 -153
-884 -174
-881 -189
-879 -198
-874 -219
-869 -238
-867 -245
-859 -272
-852 -293
-846 -310
-839 -329
-830 -351
-824 -365
-820 -374
-810 -395
-802 -411
-793 -428
-783 -446
-769 -470
-758 -487
-745 -507
-734 -523
-717 -546
-710 -555
-687...

output:

10316182.0506905988

result:

ok found '10316182.050690599', expected '10316182.050690599', error '0.000000000'

Test #19:

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

input:

404 10000
-4997 -198
-4993 -282
-4982 -433
-4975 -509
-4967 -582
-4962 -623
-4933 -821
-4925 -868
-4915 -924
-4898 -1009
-4881 -1089
-4872 -1128
-4863 -1166
-4838 -1266
-4815 -1351
-4802 -1397
-4779 -1473
-4754 -1552
-4693 -1728
-4666 -1799
-4627 -1898
-4619 -1917
-4592 -1981
-4537 -2104
-4516 -2149...

output:

95669905.9726321101

result:

ok found '95669905.972632110', expected '95669905.972632110', error '0.000000000'

Test #20:

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

input:

888 10000
-9119 -134
-9118 -188
-9117 -234
-9116 -268
-9114 -330
-9113 -357
-9108 -467
-9106 -505
-9102 -573
-9098 -634
-9096 -661
-9092 -714
-9087 -775
-9076 -895
-9070 -953
-9066 -990
-9060 -1044
-9053 -1101
-9045 -1166
-9042 -1190
-9039 -1213
-9030 -1278
-9013 -1393
-9002 -1462
-8996 -1498
-8986 ...

output:

263523679.5084166527

result:

ok found '263523679.508416653', expected '263523679.508416623', error '0.000000000'

Test #21:

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

input:

333 10000
-832 -233
-844 -216
-846 -213
-854 -201
-860 -192
-865 -184
-868 -179
-871 -173
-873 -169
-877 -161
-878 -159
-879 -157
-887 -140
-894 -122
-895 -119
-896 -116
-898 -109
-902 -94
-906 -73
-909 -56
-910 -49
-911 -40
-913 -17
-914 -3
-913 20
-909 74
-908 86
-907 94
-905 109
-902 129
-900 142...

output:

9914565.5701116584

result:

ok found '9914565.570111658', expected '9914565.570111660', error '0.000000000'

Test #22:

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

input:

414 10000
107 794
158 789
201 784
225 781
238 779
254 776
259 775
264 774
278 771
287 769
304 765
308 764
324 760
328 759
332 758
343 755
350 753
385 743
399 739
409 736
419 733
446 724
452 722
463 718
498 705
514 699
522 696
535 691
561 681
566 679
579 673
587 669
589 668
591 667
601 662
605 660
61...

output:

10783650.2566046715

result:

ok found '10783650.256604671', expected '10783650.256604670', error '0.000000000'

Test #23:

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

input:

666 10000
-294 883
-290 884
-278 887
-270 889
-266 890
-261 891
-246 894
-241 895
-225 898
-219 899
-213 900
-182 905
-175 906
-168 907
-160 908
-150 909
-140 910
-128 911
-116 912
-90 914
-76 915
-39 917
-19 918
1 919
15 918
28 917
40 916
64 914
75 913
93 911
101 910
109 909
124 907
139 905
146 904...

output:

10214064.8218686599

result:

ok found '10214064.821868660', expected '10214064.821868660', error '0.000000000'

Test #24:

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

input:

777 10000
769 412
775 403
777 400
781 394
784 389
788 382
792 375
799 362
800 360
801 358
802 356
803 354
804 352
811 338
812 336
813 334
814 332
816 328
817 326
819 321
824 308
830 292
833 284
836 275
837 272
839 266
840 263
842 257
843 254
844 251
845 248
847 242
848 239
849 236
850 233
851 230
85...

output:

10499024.5674780272

result:

ok found '10499024.567478027', expected '10499024.567478029', error '0.000000000'

Test #25:

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

input:

969 10000
352 -559
348 -560
344 -561
336 -563
328 -565
310 -569
301 -571
296 -572
291 -573
281 -575
276 -576
266 -578
261 -579
256 -580
251 -581
246 -582
230 -585
219 -587
208 -589
191 -592
185 -593
179 -594
173 -595
167 -596
161 -597
154 -598
147 -599
139 -600
131 -601
123 -602
114 -603
101 -604
85...

output:

10610264.5904448144

result:

ok found '10610264.590444814', expected '10610264.590444816', error '0.000000000'

Test #26:

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

input:

1000 10000
-331 734
-328 735
-325 736
-322 737
-319 738
-313 740
-306 742
-299 744
-292 746
-288 747
-284 748
-280 749
-276 750
-268 752
-264 753
-260 754
-252 756
-248 757
-235 760
-226 762
-217 764
-212 765
-207 766
-202 767
-192 769
-187 770
-177 772
-172 773
-167 774
-156 776
-145 778
-128 781
-...

output:

10215997.7050761208

result:

ok found '10215997.705076121', expected '10215997.705076119', error '0.000000000'

Test #27:

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

input:

1000 10000
-545 159
-544 161
-543 163
-542 165
-540 169
-539 171
-537 175
-536 177
-535 179
-534 181
-533 183
-532 185
-530 189
-529 191
-526 196
-523 201
-519 207
-517 210
-515 213
-513 216
-511 219
-508 223
-504 228
-503 229
-502 230
-501 231
-500 232
-498 234
-495 237
-494 238
-493 239
-491 241
-...

output:

8089958.1991278641

result:

ok found '8089958.199127864', expected '8089958.199127864', error '0.000000000'

Test #28:

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

input:

1000 10000
-674 -603
-678 -598
-682 -593
-686 -588
-690 -583
-693 -579
-696 -575
-699 -571
-702 -567
-711 -555
-717 -547
-720 -543
-725 -536
-730 -529
-735 -522
-737 -519
-739 -516
-741 -513
-743 -510
-745 -507
-747 -504
-749 -501
-753 -495
-758 -487
-761 -482
-764 -477
-768 -470
-772 -463
-780 -449...

output:

10330585.4913331699

result:

ok found '10330585.491333170', expected '10330585.491333170', error '0.000000000'

Test #29:

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

input:

1000 10000
-642 678
-639 681
-637 683
-635 685
-627 693
-626 694
-625 695
-624 696
-623 697
-622 698
-620 700
-619 701
-618 702
-615 705
-606 713
-600 718
-590 726
-586 729
-582 732
-578 735
-575 737
-569 741
-566 743
-563 745
-560 747
-557 749
-554 751
-548 755
-543 758
-538 761
-529 766
-520 771
-...

output:

10366414.3197384700

result:

ok found '10366414.319738470', expected '10366414.319738468', error '0.000000000'

Test #30:

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

input:

1337 10000
-4231 3240
-4225 3249
-4221 3255
-4208 3274
-4191 3298
-4181 3312
-4178 3316
-4147 3357
-4137 3370
-4122 3389
-4106 3409
-4093 3425
-4058 3468
-4053 3474
-4027 3504
-4018 3514
-4008 3525
-3994 3540
-3964 3572
-3948 3589
-3931 3607
-3911 3628
-3889 3651
-3878 3662
-3877 3663
-3874 3666
-38...

output:

100313919.0073064417

result:

ok found '100313919.007306442', expected '100313919.007306457', error '0.000000000'

Test #31:

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

input:

1990 10000
-2727 8649
-2705 8654
-2647 8667
-2593 8679
-2575 8683
-2566 8685
-2543 8690
-2524 8694
-2505 8698
-2476 8704
-2447 8710
-2378 8724
-2373 8725
-2368 8726
-2363 8727
-2327 8734
-2275 8744
-2228 8753
-2196 8759
-2168 8764
-2114 8773
-2102 8775
-2096 8776
-2066 8781
-2060 8782
-2011 8790
-19...

output:

270479672.7122440338

result:

ok found '270479672.712244034', expected '270479672.712244034', error '0.000000000'

Test #32:

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

input:

2000 10000
6530 -6566
6508 -6589
6484 -6614
6433 -6665
6423 -6675
6409 -6689
6393 -6705
6386 -6712
6379 -6719
6375 -6723
6373 -6725
6355 -6743
6344 -6754
6335 -6763
6328 -6770
6312 -6786
6308 -6790
6305 -6793
6299 -6799
6237 -6860
6208 -6888
6195 -6900
6182 -6912
6170 -6923
6159 -6933
6148 -6943
613...

output:

269303715.6403097510

result:

ok found '269303715.640309751', expected '269303715.640309751', error '0.000000000'

Test #33:

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

input:

999 10000
-534 53
832 126
-317 -71
-30 36
626 -68
-201 250
12 -157
293 118
-400 0
49 153
-769 50
-136 -156
86 139
-309 -59
263 196
284 -42
-158 -247
-385 123
258 266
-676 -269
-959 -158
119 216
761 37
638 -111
202 114
301 25
-163 168
91 -126
-847 136
411 23
522 269
-533 247
459 210
-469 160
63 261
7...

output:

10375582.1408991553

result:

ok found '10375582.140899155', expected '10375582.140899157', error '0.000000000'

Test #34:

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

input:

999 10000
131 160
-372 -79
684 -264
512 -97
601 -91
-146 -16
-294 -163
-513 -142
52 39
411 -249
-186 -193
481 157
243 -159
-72 -280
461 125
-116 253
-210 71
-168 -51
-50 69
655 102
391 37
-257 -18
775 12
228 195
-771 -37
231 274
521 184
123 176
457 30
898 96
-512 270
-93 98
-681 -12
-87 204
-587 44
...

output:

10437570.0111656785

result:

ok found '10437570.011165679', expected '10437570.011165679', error '0.000000000'

Test #35:

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

input:

1000 10000
290 -174
633 -147
-57 479
25 -150
-540 454
-530 -69
-209 -172
396 -317
496 -174
535 119
-384 -182
-456 509
-27 424
-286 -80
526 -144
391 -498
-482 -391
-4 -25
-172 -63
724 -457
341 580
596 274
-565 -373
616 -47
-292 -484
-603 -542
245 39
643 -546
-371 -533
568 -18
708 498
-623 100
560 -48...

output:

10508648.6558468062

result:

ok found '10508648.655846806', expected '10508648.655846806', error '0.000000000'

Test #36:

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

input:

1000 10000
526 -442
-212 -42
762 57
-123 -159
62 229
-680 499
108 -504
681 62
-662 167
-533 342
411 568
44 -372
-733 -525
770 -519
612 -382
-318 18
-676 -232
688 -335
-609 101
-326 559
-283 306
173 377
577 242
-598 -418
707 -429
-400 79
-484 18
-9 -500
747 228
142 447
152 -267
-339 57
-621 -83
367 5...

output:

10604345.2209559456

result:

ok found '10604345.220955946', expected '10604345.220955947', error '0.000000000'

Test #37:

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

input:

1000 10000
834 57
546 -148
-819 259
-682 273
-670 158
-815 -162
368 -67
-70 2
637 -327
-194 12
586 86
456 -213
406 -173
621 326
-300 -319
-720 -191
-372 314
-700 152
-61 168
442 291
-746 -285
-107 -284
43 -217
278 144
-281 219
730 -79
-602 134
728 -45
-423 -226
-203 -66
493 34
88 -310
496 318
-751 1...

output:

10388137.5820510052

result:

ok found '10388137.582051005', expected '10388137.582051003', error '0.000000000'

Test #38:

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

input:

1000 10000
-740 -49
-31 -186
-276 0
-238 -292
-729 72
-398 40
873 275
880 -35
-455 -340
108 269
-811 -96
-334 -298
161 309
56 -64
-723 6
-92 -274
-492 42
-189 236
216 305
292 190
740 -22
-531 -338
-341 -307
-39 166
535 350
-648 -65
668 311
-122 -3
826 -344
-423 -13
465 215
-293 72
210 -201
869 331
-...

output:

10454566.1479555592

result:

ok found '10454566.147955559', expected '10454566.147955561', error '0.000000000'

Test #39:

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

input:

1337 10000
-2878 -2727
-4370 -5490
7333 5040
-2042 -5191
-3271 -5053
3263 -2381
-4162 1923
3018 902
-1568 6003
4799 -399
-1147 2006
-6050 -382
-314 -4319
5404 341
-4007 4126
-3104 -1345
7335 -785
3987 1878
-4444 -4837
-4968 -496
6554 1702
1856 864
-575 -4720
7307 -5430
-5093 -4110
804 3944
-6122 -34...

output:

219296853.7499537766

result:

ok found '219296853.749953777', expected '219296853.749953777', error '0.000000000'

Test #40:

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

input:

2000 10000
3554 513
1816 3147
2928 1514
4408 4161
3937 4156
224 3447
225 5555
800 944
2706 3010
6523 2293
4390 1329
3656 1377
6662 4434
2580 3601
2560 1406
6021 4870
2571 2865
3979 3642
4948 4900
6161 927
2243 1329
835 4674
3746 3193
792 5882
2489 4800
5058 6464
567 4808
957 2970
5352 5718
2396 2478...

output:

90488159.4590302408

result:

ok found '90488159.459030241', expected '90488159.459030241', error '0.000000000'

Test #41:

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

input:

60 10000
-273 -936
759 -612
-108 -969
-969 108
780 585
969 108
612 -759
585 780
-969 -108
-780 585
-240 945
-375 900
-240 -945
-495 840
375 900
240 -945
840 495
-780 -585
-945 -240
-936 -273
-840 495
-900 -375
-585 780
-900 375
495 840
-585 -780
240 945
0 -975
-273 936
969 -108
936 273
780 -585
-975...

output:

11284271.6733942553

result:

ok found '11284271.673394255', expected '11284271.673394255', error '0.000000000'

Test #42:

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

input:

28 10000
-800 -600
960 280
936 352
-936 352
-280 -960
800 -600
-280 960
-960 -280
600 -800
936 -352
-960 280
-800 600
-600 800
352 -936
-936 -352
800 600
280 960
280 -960
-600 -800
960 -280
0 1000
-1000 0
1000 0
600 800
0 -1000
-352 -936
-352 936
352 936

output:

11591174.9366116673

result:

ok found '11591174.936611667', expected '11591174.936611665', error '0.000000000'

Test #43:

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

input:

4 10000
0 -1337
-1337 0
1337 0
0 1337

output:

15157569.0000000000

result:

ok found '15157569.000000000', expected '15157569.000000000', error '0.000000000'

Test #44:

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

input:

4 10000
0 -1442
0 1442
1442 0
-1442 0

output:

16499364.0000000000

result:

ok found '16499364.000000000', expected '16499364.000000000', error '0.000000000'

Test #45:

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

input:

36 10000
-8000 6000
8000 6000
-6000 -8000
-10000 0
-3520 9360
-5376 -8432
-9600 -2800
-8000 -6000
-9600 2800
-3520 -9360
-8432 -5376
5376 8432
9600 2800
2800 -9600
6000 -8000
-5376 8432
-9360 3520
8000 -6000
-2800 9600
8432 5376
5376 -8432
10000 0
9360 -3520
8432 -5376
3520 -9360
0 -10000
-8432 5376...

output:

311369015.6237308979

result:

ok found '311369015.623730898', expected '311369015.623730958', error '0.000000000'

Test #46:

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

input:

1000 10000
883 352
847 352
936 269
208 -352
-40 -352
-134 -352
70 -352
36 -352
128 352
-829 -352
-936 139
-370 -352
-936 -184
936 219
936 38
-936 -111
358 352
417 352
221 -352
-936 106
-936 239
-549 -352
936 136
450 -352
-585 -352
-936 102
-540 -352
594 -352
670 352
148 -352
-936 -244
936 123
-756 -...

output:

10643628.3450558968

result:

ok found '10643628.345055897', expected '10643628.345055897', error '0.000000000'

Test #47:

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

input:

1000 10000
-800 -590
-447 600
724 600
762 -600
-277 600
575 600
800 467
800 581
-800 -165
800 251
-800 -167
-800 372
800 197
-800 -472
440 -600
649 600
699 -600
800 -391
90 -600
-680 -600
223 600
800 555
117 -600
-800 60
800 142
-417 600
800 -181
-208 600
-779 600
-800 66
-599 600
392 600
-294 -600
...

output:

10951394.2064832374

result:

ok found '10951394.206483237', expected '10951394.206483237', error '0.000000000'

Test #48:

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

input:

2000 10000
8000 5735
8000 1105
8000 2187
2079 -6000
4785 6000
-5460 -6000
8000 -3274
8000 -1281
3772 -6000
-2676 -6000
5094 -6000
-8000 -4862
6476 6000
1568 6000
-8000 -1100
4427 6000
6356 6000
8000 320
-1414 -6000
7542 6000
8000 5321
515 -6000
-4864 -6000
8000 -1288
2946 -6000
8000 -1154
-8000 -539...

output:

223988195.5000000000

result:

ok found '223988195.500000000', expected '223988195.500000000', error '0.000000000'

Test #49:

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

input:

2 10000
8 -69
48 44

output:

601185.8187081150

result:

ok found '601185.818708115', expected '601185.818708115', error '0.000000000'

Test #50:

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

input:

6 10000
10 -8
4 -1
-5 6
-2 -2
7 6
-1 0

output:

102685.4226434185

result:

ok found '102685.422643418', expected '102685.422643416', error '0.000000000'

Test #51:

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

input:

6 10000
-6 10
-5 -1
-3 -1
-4 -1
-2 -9
9 9

output:

105596.6155486457

result:

ok found '105596.615548646', expected '105596.615548645', error '0.000000000'

Test #52:

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

input:

6 10000
5 10
9 4
-2 10
7 -3
9 0
-4 7

output:

79158.4415042121

result:

ok found '79158.441504212', expected '79158.441504209', error '0.000000000'

Test #53:

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

input:

10 10000
-9 -1
-8 -1
10 8
-4 9
7 -5
-4 8
1 9
3 10
-8 8
10 5

output:

105250.4802081431

result:

ok found '105250.480208143', expected '105250.480208143', error '0.000000000'

Test #54:

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

input:

5 10000
6 10
4 3
0 -1
8 -5
-9 8

output:

107128.6727951649

result:

ok found '107128.672795165', expected '107128.672795163', error '0.000000000'

Test #55:

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

input:

47 10000
-168 -33
-57 -58
119 -15
-179 -10
-33 6
-15 -146
-113 4
-125 185
-102 42
-99 171
162 -95
66 196
82 -25
151 123
-2 0
22 13
-2 48
-30 83
50 163
182 -16
133 197
130 125
189 -63
-168 89
36 -24
-67 89
-64 -87
54 -44
-160 -24
173 59
64 -23
197 -73
143 -31
134 -163
32 140
175 38
-113 161
124 21
19...

output:

2513500.1060920190

result:

ok found '2513500.106092019', expected '2513500.106092019', error '0.000000000'

Test #56:

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

input:

84 10000
-211 -173
488 -224
-114 -383
83 -457
-197 23
40 -159
382 -190
-129 -234
-393 140
414 -433
-313 -203
278 -352
263 101
-440 -209
-449 -288
-47 -450
-179 16
119 -323
130 -180
353 -238
-136 -486
18 -204
261 356
90 459
403 -395
-160 230
-228 -83
385 319
318 338
493 -179
-434 463
-440 454
-363 -3...

output:

6598635.0883843973

result:

ok found '6598635.088384397', expected '6598635.088384395', error '0.000000000'

Test #57:

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

input:

77 10000
98 70
-457 -320
172 -290
51 -219
167 324
280 -371
-246 43
-139 -16
-194 400
-495 -15
-93 170
-104 -455
-124 98
456 -222
-415 -233
476 -209
-437 43
-138 -84
-107 -329
-452 270
-344 -271
419 -320
-146 -266
441 223
-319 206
-482 -182
-402 15
169 73
131 460
-61 443
-186 463
-382 360
68 355
-415...

output:

6224748.1368105104

result:

ok found '6224748.136810510', expected '6224748.136810511', error '0.000000000'

Test #58:

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

input:

54 10000
231 -200
497 162
250 -169
116 418
281 41
372 -224
-360 -359
-295 -428
433 -395
356 203
-367 313
146 339
-319 -341
436 -254
356 479
197 99
389 -257
356 265
29 448
-196 -225
388 379
131 171
277 -121
-336 -146
-292 -168
266 -446
-309 309
-406 306
-120 460
292 204
-76 -389
222 -486
18 140
-176 ...

output:

6570138.2358367937

result:

ok found '6570138.235836794', expected '6570138.235836793', error '0.000000000'

Test #59:

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

input:

52 10000
387 -43
455 -79
113 438
-117 16
405 -319
193 -372
-37 243
-98 439
-378 487
-294 442
150 -215
-279 479
169 82
-283 269
-342 -375
22 92
-482 187
273 -62
-68 300
-87 52
-255 -63
176 32
304 -103
175 -412
297 -173
446 197
-133 241
482 -174
489 212
186 217
-337 404
-418 -106
-304 108
275 6
-367 1...

output:

6713656.4826568430

result:

ok found '6713656.482656843', expected '6713656.482656839', error '0.000000000'

Test #60:

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

input:

500 10000
2912 2068
-1857 -5889
3451 5250
-5424 -6052
-5094 -8101
2370 5778
-5391 -5865
-5231 3020
904 7610
-2295 8305
905 4727
1257 -5609
-3135 732
-9600 966
1734 8004
6678 -434
-9092 -589
1722 -6282
5159 3009
5551 -2328
-1223 -7367
-1311 -6985
-2993 2147
-3957 6807
-507 -4061
-3545 589
-6480 6046
...

output:

295762370.3703521490

result:

ok found '295762370.370352149', expected '295762370.370352209', error '0.000000000'

Test #61:

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

input:

500 10000
-4587 6794
1117 2177
-2364 -9436
-2398 3305
6990 2259
-3446 8587
-8063 -3176
-4715 -4623
-4218 -5596
4358 6997
177 -5500
-5799 -3211
6131 -1636
-2616 -8086
6299 5884
3824 4185
2204 3034
-4264 6320
2503 -5453
-6741 1702
2812 -4370
6608 1840
-1540 3787
-3435 -8481
-5470 -3282
1040 6820
-4201...

output:

299721620.3826874495

result:

ok found '299721620.382687449', expected '299721620.382687390', error '0.000000000'

Test #62:

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

input:

500 10000
4319 -6684
7420 6624
-2399 -1526
1828 9682
1246 -4525
8440 -865
4791 1178
-6227 4390
-8516 -4870
-8546 754
5740 -1434
8307 -4212
-4297 5292
-5990 -2998
6447 -3739
-8734 2640
-2761 9326
-5002 2577
-4249 2588
-6586 1142
1577 3141
2704 6641
-5714 -5342
-4288 8832
-4415 428
3273 -4005
-7573 -3...

output:

298203203.3688006401

result:

ok found '298203203.368800640', expected '298203203.368800640', error '0.000000000'

Test #63:

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

input:

500 10000
-6097 7374
8312 846
124 -5803
6375 3283
-2670 422
-5558 2918
8863 -410
7772 -2165
870 6300
7135 6279
-228 7000
-2017 -677
-6289 -1055
3856 -5253
4133 -2570
7971 2712
-1334 -1164
-678 -5035
-7838 -1082
-1174 -4612
-3729 7539
-4830 -7014
-3421 1807
-4378 -3076
7786 -3288
6031 -3275
-8551 -25...

output:

298784143.2109546661

result:

ok found '298784143.210954666', expected '298784143.210954666', error '0.000000000'

Test #64:

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

input:

500 10000
59 -7419
-9665 2198
2630 -1294
-694 3376
-30 -8821
-1956 4581
939 -1257
1078 9080
6894 493
-280 3275
-8355 4055
3595 5608
-4388 6866
1437 -6139
8014 5956
-4021 6475
8864 1265
4737 -753
5983 -5922
3514 -6293
6013 -6868
9464 -1482
9411 -542
-1237 -197
3353 7936
3431 -2531
-4904 -1917
-3632 2...

output:

296501733.0517057776

result:

ok found '296501733.051705778', expected '296501733.051705778', error '0.000000000'

Test #65:

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

input:

500 10000
-529 -7642
-4705 190
-9882 945
-8473 -4822
1272 3359
-6340 -3294
-8120 -5396
2457 2939
-4098 -3153
4742 -6988
-2740 -6277
-261 -4590
1275 -404
4378 -2571
1307 -294
915 508
4663 -5385
-1936 5565
-7597 4927
734 -4611
-7850 -1343
4768 1074
4032 -4940
-4847 -5017
3009 8885
-4978 5574
-6798 263...

output:

298623356.9871844649

result:

ok found '298623356.987184465', expected '298623356.987184465', error '0.000000000'

Test #66:

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

input:

500 10000
6010 -7688
3757 -6845
-9181 -94
1823 -4354
1710 -266
-1584 7905
5855 2825
2119 -5762
2021 -4642
5319 560
5127 -5108
-1281 6452
-4653 5738
2823 5699
5655 -2177
1146 -3718
-445 -4649
2472 -103
4138 -212
4726 -8514
4363 3763
5207 4781
-1887 -3616
2706 -2733
-5269 839
-1755 -1148
3659 9040
-12...

output:

299933401.1391092539

result:

ok found '299933401.139109254', expected '299933401.139109254', error '0.000000000'

Test #67:

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

input:

500 10000
-7173 4155
-1473 -9595
6758 5662
1176 -1512
8474 -1084
-3787 5745
1034 7475
3508 1913
-3023 -1043
-4568 -5013
-5898 -1719
-2948 -6468
-3598 -4369
-6327 6692
-870 -1599
5805 6540
-7161 -3982
-2984 -4515
-1880 -9111
-1100 2786
7593 -3562
-2475 -4605
1302 -7874
-7010 -1263
2641 3777
-6391 754...

output:

301058794.3933868408

result:

ok found '301058794.393386841', expected '301058794.393386781', error '0.000000000'

Test #68:

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

input:

500 10000
6263 -5304
-3705 -6173
-3001 -3640
3936 4265
-2229 -5025
-895 -1525
612 4346
-4449 8777
5338 -7926
-2528 8780
4043 4839
1373 -4181
3488 -1510
90 -9565
1430 -7178
6954 3724
2815 -8479
-4141 -3004
8782 201
136 -861
-8930 -1155
8307 -613
941 -1094
-7821 -724
-5169 3590
453 -1859
1397 -7922
-1...

output:

298471613.6850226521

result:

ok found '298471613.685022652', expected '298471613.685022652', error '0.000000000'

Test #69:

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

input:

500 10000
-3106 7114
348 6756
-657 1591
601 8955
0 -5929
-6342 5184
-1157 4930
5843 -783
3766 6849
4057 -8759
8212 4723
3027 1419
867 -9010
4899 3930
-8122 2991
3409 7861
-4241 4847
8293 874
8997 1936
5047 4139
-1191 -3641
6205 1468
-1730 6285
-8205 1670
1796 7296
-4300 823
-3570 -973
2155 -2803
-30...

output:

298467959.2960076928

result:

ok found '298467959.296007693', expected '298467959.296007693', error '0.000000000'

Test #70:

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

input:

1000 10000
300 4010
9159 -422
-2258 1282
-4409 748
-3518 4699
-7242 -3085
1208 -1773
-8698 4847
8186 -1622
2657 2239
8841 -4139
-2098 9744
-4888 3273
1705 -4960
4015 6961
-4357 -8817
-8230 4691
-6741 3933
4634 7122
-115 3936
-50 -7040
573 -9892
-4678 4002
-832 -4878
8593 3864
-134 -2646
2446 7820
-1...

output:

306968204.0550791025

result:

ok found '306968204.055079103', expected '306968204.055079103', error '0.000000000'

Test #71:

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

input:

1000 10000
-1765 342
11 -2841
3037 9316
799 -4537
5409 -5943
-3728 -8261
-1857 -2666
8557 -4371
-6398 -4276
-19 685
8188 538
-4211 -469
7716 482
-5636 528
7699 -3447
7210 4470
2035 -211
4619 -4590
-5508 -3540
2589 -3467
707 -3854
8199 -4413
5196 -7821
3898 -2397
-938 -6444
-6488 4945
-2859 9216
-946...

output:

303071525.0798929930

result:

ok found '303071525.079892993', expected '303071525.079892993', error '0.000000000'

Test #72:

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

input:

1000 10000
63 5240
5874 -4593
-8574 -5082
6538 7100
-4634 -154
-7613 2894
3764 6986
-6443 2773
8893 -853
886 -6512
-5245 -1685
-3500 -6120
-8408 -3380
1034 -5262
5352 3448
1999 1692
-1698 246
6249 1949
1044 2668
4794 1592
-8310 -611
-408 5203
2552 -3354
-5524 -5832
-1342 -2494
-1278 8566
-1412 -1283...

output:

304206047.9974822998

result:

ok found '304206047.997482300', expected '304206047.997482300', error '0.000000000'

Test #73:

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

input:

1000 10000
-8237 1703
-291 -1654
8676 -2616
1039 8741
830 1164
3173 -2975
-1842 1504
-5081 3521
9126 -4058
-255 -6796
4027 2653
-6489 -2286
-2473 -7826
3964 -461
-344 -2922
2743 1196
-1646 2016
-8112 901
-1533 7523
-3360 -1644
810 -2223
4795 -7382
160 6615
-356 6726
7212 3337
1478 8109
-5990 -7650
-...

output:

305429202.4828569293

result:

ok found '305429202.482856929', expected '305429202.482856989', error '0.000000000'

Test #74:

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

input:

1000 10000
4114 -5067
-210 7291
-2962 6814
1739 3612
-4134 1515
5488 -5850
8329 674
3261 -4997
7145 6407
-5714 -1496
-8950 1555
-1148 543
-2891 -9438
-2293 -497
-9994 14
-3319 -1479
-426 -7367
2037 -7345
5173 444
4873 7307
1655 5349
5615 -1835
-8691 4215
-8837 3563
-2245 4636
-6612 286
-144 -5245
37...

output:

303937679.9028702974

result:

ok found '303937679.902870297', expected '303937679.902870297', error '0.000000000'

Test #75:

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

input:

1000 10000
-5712 4882
4776 4954
5912 491
-3771 5419
-4243 2505
-6271 -5923
6345 -3657
-5176 -5221
900 1927
7682 -4857
2721 3182
-4266 -4297
8533 -3125
-440 -4678
5057 2712
-5439 6767
-7048 -5537
-636 9215
-8839 -2970
-831 -1115
370 -5060
4570 -8303
-5326 -5197
-5781 7216
-3149 -8186
5452 6724
-2288 ...

output:

303926285.0352824926

result:

ok found '303926285.035282493', expected '303926285.035282493', error '0.000000000'

Test #76:

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

input:

1000 10000
-4949 3214
-1751 7195
-7863 -450
7102 -6130
-773 3349
4306 -1899
-6688 -860
5955 -1130
-6564 -3320
-8745 -884
-4365 3446
-603 7069
1050 -3207
3918 -2046
-7226 605
-4545 -6302
-7657 -4171
-8159 1286
-1582 -4890
-5841 4188
-5654 4297
-7659 6250
-1138 -9828
-4940 -1101
6525 7388
-5098 7750
-...

output:

304989248.0064021945

result:

ok found '304989248.006402194', expected '304989248.006402135', error '0.000000000'

Test #77:

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

input:

1000 10000
-8231 1927
4630 8141
9398 -2996
-1864 -5650
162 -3486
-5092 -4361
-371 3425
-4914 -5985
-7781 2064
4602 7077
-2626 -2815
-1129 -4812
-1517 3805
9081 -1993
640 2380
-7880 4231
-2420 839
870 2882
245 -9552
-5316 -4020
8752 -4044
-9462 -1865
-7170 -123
4372 -4055
-3780 -4687
1941 9576
762 54...

output:

303987652.6500679255

result:

ok found '303987652.650067925', expected '303987652.650067925', error '0.000000000'

Test #78:

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

input:

1000 10000
-7806 4404
-3200 -4809
-3116 7725
1074 6207
6185 6823
-1824 -2090
-6132 -1119
966 179
-2594 -7469
8494 1043
-3808 6535
-9473 -2941
-6572 -1994
7161 -14
-4639 -1017
5282 -410
4273 -8114
306 7590
-8397 -4193
2335 -2869
-1570 705
-7160 -3147
18 878
2362 -7746
-1905 -5976
-7320 -384
-7330 184...

output:

305031180.2148645520

result:

ok found '305031180.214864552', expected '305031180.214864552', error '0.000000000'

Test #79:

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

input:

6900 10000
7283 2262
2139 6230
1272 32
-867 -6079
5305 -608
-6249 -3680
2748 8510
-976 4690
-2304 4228
-1861 -9277
8584 5072
8676 -2679
250 -4001
9115 3714
-5787 -2517
-5320 7634
-4471 -7731
3017 2700
-4398 7531
5227 8476
9251 869
-9490 319
5732 2094
8152 -1130
4922 2681
-5771 847
-2203 5155
-9086 3...

output:

311085021.9688946605

result:

ok found '311085021.968894660', expected '311085021.968894720', error '0.000000000'

Test #80:

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

input:

4431 10000
921 8617
5511 6372
-3602 4590
6027 4885
2954 -8581
6906 -2603
-1137 8407
4004 -4869
3720 -3906
-6989 6698
4327 -1382
1252 -4318
-1215 8586
6347 -1455
1366 4652
-6749 4688
-3358 -3116
6804 6171
-3385 -424
5495 -6564
3958 -2
8528 2694
-2200 7775
5132 -3820
-1062 6505
-3125 -3709
1049 9731
-...

output:

310317753.1712296605

result:

ok found '310317753.171229661', expected '310317753.171229720', error '0.000000000'

Test #81:

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

input:

8340 10000
8986 -327
-4187 -7146
-7509 5972
1526 -394
1544 3121
8608 -599
-3034 -3484
6794 1924
-1797 -4491
-8199 1758
-3605 1598
-4422 7105
-39 5902
1326 -6395
-3671 -7007
-8715 3089
-2350 -5381
-2199 7987
4287 -624
-9297 3091
5477 7527
5223 4942
2616 -2206
4391 5710
8117 5588
-1684 -757
4955 -1554...

output:

311819360.1967970133

result:

ok found '311819360.196797013', expected '311819360.196797013', error '0.000000000'

Test #82:

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

input:

8462 10000
7378 -3494
-2203 -3687
-2240 -1055
764 1240
871 -4122
-2628 -5858
-3616 6567
6366 7306
-2302 4934
7681 -2896
-3830 4173
-6728 -6672
-4385 8234
3851 -5258
-2549 8629
1120 -8539
3020 -8442
-4968 -1045
4367 -6366
8243 5635
3431 -3257
-1545 8925
1183 5426
5095 2338
3515 -4726
5387 -7948
-8836...

output:

311796650.1656939387

result:

ok found '311796650.165693939', expected '311796650.165693939', error '0.000000000'

Test #83:

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

input:

2577 10000
2108 -8388
7568 1453
2877 7133
-5071 4214
6696 -3860
2465 -2404
3938 -9115
208 2037
-2045 -5771
-6987 6804
-2791 1229
-991 -3651
-8782 4486
-2757 9140
2205 -360
3990 5382
4655 -4732
-8530 3
653 -1112
-1736 755
-2968 -5766
2856 -6039
4408 -8847
1085 5656
-1664 -1500
8160 1861
7601 -1585
-1...

output:

309180620.2808783054

result:

ok found '309180620.280878305', expected '309180620.280878305', error '0.000000000'

Test #84:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314026741.7801103592

result:

ok found '314026741.780110359', expected '314026741.780110359', error '0.000000000'

Test #85:

score: 0
Accepted
time: 13ms
memory: 4372kb

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314027422.7801103592

result:

ok found '314027422.780110359', expected '314027422.780110359', error '0.000000000'

Test #86:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9944 -1036
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314027385.2801103592

result:

ok found '314027385.280110359', expected '314027385.280110359', error '0.000000000'

Test #87:

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

input:

1000 10000
-9999 -135
-9995 -246
-9995 -279
-9993 -347
-9992 -396
-9989 -439
-9986 -524
-9985 -544
-9982 -564
-9982 -598
-9979 -633
-9973 -721
-9970 -748
-9967 -811
-9963 -845
-9957 -916
-9954 -957
-9949 -1008
-9945 -1037
-9937 -1104
-9928 -1197
-9921 -1253
-9914 -1308
-9909 -1346
-9892 -1465
-9873 ...

output:

314055597.5000000000

result:

ok found '314055597.500000000', expected '314055597.500000000', error '0.000000000'

Test #88:

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

input:

1000 10000
-9998 -136
-9996 -245
-9994 -281
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9970 -748
-9966 -809
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314027308.2801103592

result:

ok found '314027308.280110359', expected '314027308.280110359', error '0.000000000'

Test #89:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9990 -398
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314029000.6305503249

result:

ok found '314029000.630550325', expected '314029000.630550325', error '0.000000000'

Test #90:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314031186.2801103592

result:

ok found '314031186.280110359', expected '314031186.280110359', error '0.000000000'

Test #91:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9982 -564
-9981 -599
-9980 -631
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314028812.5000000000

result:

ok found '314028812.500000000', expected '314028812.500000000', error '0.000000000'

Test #92:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9964 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9890 -1464
-9874 ...

output:

314029155.7801103592

result:

ok found '314029155.780110359', expected '314029155.780110359', error '0.000000000'

Test #93:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9990 -398
-9989 -440
-9986 -524
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9956 -915
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314033570.3752691746

result:

ok found '314033570.375269175', expected '314033570.375269175', error '0.000000000'

Test #94:

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

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9986 -526
-9984 -545
-9982 -563
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9958 -915
-9953 -958
-9947 -1009
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1307
-9909 -1346
-9892 -1465
-9874 ...

output:

314041577.4565979838

result:

ok found '314041577.456597984', expected '314041577.456597984', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed