QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209772#7568. Keychainucup-team1209AC ✓9417ms6476kbC++207.3kb2023-10-10 17:15:082023-10-10 17:15:09

Judging History

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

  • [2023-10-10 17:15:09]
  • 评测
  • 测评结果:AC
  • 用时:9417ms
  • 内存:6476kb
  • [2023-10-10 17:15:08]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = long double;
const db eps = 1e-4;
const db pi = std::acos(-1);
std::mt19937 gen;


db sgn(db x, db eps) { return x < -eps ? -1 : x > eps; }
db sgn(db x) { return x < -eps ? -1 : x > eps; }
db eq(db x, db y) { return !sgn(x - y); }
struct vec2 {
	db x, y;
	db abs() const { return std::sqrt(x * x + y * y); }
};
vec2 r90(vec2 x) { return {-x.y, x.x}; }
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator / (vec2 x, db y) { return {x.x / y, x.y / y}; }
vec2 operator * (vec2 x, db y) { return {x.x * y, x.y * y}; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }

struct line : vec2 {
	db z;
	line() = default;
	line(db a, db b, db c) : vec2{a, b}, z(c) {}
	line(vec2 a, vec2 b) : vec2(r90(b - a)), z(a * b) { }
	db operator ()(vec2 a) const { return a % vec2(*this) + z; }
	line perp() const { return {y, -x, 0}; } // 垂直
	line para(vec2 o) { return {x, y, z - (*this)(o)}; } // 平行
	bool test(vec2 o) const {
		using f128 = __float128;
		return (f128) o.x * x + (f128) o.y * y + z >= 0;
	}
};
vec2 operator & (line x, line y) {
	return vec2{vec2{x.z, x.y} * vec2{y.z, y.y}, vec2{x.x, x.z} * vec2{y.x, y.z}} / -(vec2(x) * vec2(y));
}
std::tuple<ll, ll, ll> operator && (line x, line y) {
	ll A = round(vec2{x.z, x.y} * vec2{y.z, y.y} * 4);
	ll B = round(vec2{x.x, x.z} * vec2{y.x, y.z} * 4);
	ll C = round(-(vec2(x) * vec2(y)) * 4);
	if(C < 0) {
		A *= -1;
		B *= -1;
		C *= -1;
	}
	int lg = __builtin_ctzll(A | B | C);
	return std::make_tuple(A >> lg, B >> lg, C >> lg);
}
line bisector(vec2 x, vec2 y) { return line(y, x).perp().para((x + y) / 2); } // x 在半平面一侧
bool is_para(line x, line y) { return eq(vec2(x) * vec2(y), 0); } // 判断线平行
db det(const line & a, const line & b, const line & c) {
	//using f128 = __float128;
	vec2 A = a, B = b, C = c;
	using f128 = db;
	return c.z * f128(A * B) + a.z * f128(B * C) + b.z * f128(C * A);
}
db check(const line & a, const line & b, const line & c) {
	return sgn(det(a, b, c), 0.25) * sgn(vec2(a) * vec2(b));
}
struct seg {
	vec2 x, y;
	seg(const vec2 & A, const vec2 & B) : x(A), y(B) {}
	bool onseg(const vec2 & o) const {
		return (o - x) % (o - y) < eps && std::fabs((o - x) * (o - y)) < eps;
	}
};
int contain(const std::vector<vec2> & a, vec2 o) {
	bool in = 0;
	for(int i = 0;i < (int) a.size();++i) {
		vec2 x = a[i] - o, y = a[(i + 1) % a.size()] - o;
		if(x.y > y.y) std::swap(x, y);
		if(x.y <= eps && y.y > eps && x * y < -eps) in ^= 1;
		if(std::fabs(x * y) < eps && x % y < eps) return 2; // 在线段上,看情况改
	}
	return in;
}
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);
	//	assert(check(a, b, c) != 0);
		if(va > 0 || vb > 0 || (va == 0 && vb == 0)) {
			res.push_back(b);
		}
		if(va >= 0 && vb < 0) {
			res.push_back(l);
		}
	}
	return res;
}
const db V = 1e9;
std::vector<std::vector<line>> voronoi(std::vector<vec2> p) {
	int n = p.size();
	auto b = p; shuffle(b.begin(), b.end(), gen);
	std::vector<std::vector<line>> a(n, {
		{V, 0, V * V}, {0, V, V * V},
			{-V, 0, V * V}, {0, -V, V * V},
	});
	for(int i = 0;i < n;++i) {
		for(vec2 x : b) if((x - p[i]).abs() > eps) {
			a[i] = cut(a[i], bisector(p[i], x));
		}
	}
	return a;
}
std::vector<std::vector<line>> negvoronoi(std::vector<vec2> p) {
	int n = p.size();
	auto b = p; shuffle(b.begin(), b.end(), gen);
	std::vector<std::vector<line>> a(n, {
		{V, 0, V * V}, {0, V, V * V},
			{-V, 0, V * V}, {0, -V, V * V},
	});
	for(int i = 0;i < n;++i) {
		for(vec2 x : b) if((x - p[i]).abs() > eps) {
			a[i] = cut(a[i], bisector(x, p[i]));
			if(a[i].empty()) break;
		}
	}
	return a;
}
std::vector<vec2> gethull(std::vector<vec2> o) { 
	sort(o.begin(), o.end(), [](vec2 x, vec2 y) { return eq(x.x, y.x) ? x.y < y.y : x.x < y.x; });
	std::vector<vec2> stack;
	auto cross = [&](vec2 a, vec2 b, vec2 c) {
		return (b - a) * (c - a);
	};
	for(int i = 0;i < (int) o.size();++i) {
		for(;stack.size() >= 2 && cross(stack.rbegin()[1], stack.back(), o[i]) <= eps;) {
			stack.pop_back();
		}
		stack.push_back(o[i]);
	}
	for(int i = o.size() - 2, t = stack.size();i >= 0;--i) {
		for(;stack.size() > t && cross(stack.rbegin()[1], stack.back(), o[i]) <= eps;) {
			stack.pop_back();
		}
		stack.push_back(o[i]);
	}
	stack.pop_back();
	return stack;
}
db findmax(vec2 d, const std::vector<vec2> & a) {
	int l = 0, r = a.size() - 1;
	if(a[0] % d > a.back() % d) {
		for(;l + 1 < r;) {
			int mid = (l + r) >> 1;
			if(a[mid] % d > a[l] % d && a[mid] % d > a[mid - 1] % d) {
				l = mid;
			} else {
				r = mid;
			}
		}
		return l;
	} else {
		for(;l + 1 < r;) {
			int mid = (l + r) >> 1;
			if(a[mid] % d > a[r] % d && a[mid] % d > a[mid + 1] % d) {
				r = mid;
			} else {
				l = mid;
			}
		}
		return r;
	}
} // 完整凸包二分求极值


int main() {
#ifdef zqj
	freopen("$.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false), cin.tie(0);
	int n;
	n = 3000;
	cin >> n;
	std::mt19937 gen(142);

	std::vector<vec2> a(n);
	for(int i = 0;i < n;++i) {
//		a[i].x = gen() %  100000 + 1;
//		a[i].y = gen() %  100000 + 1;
		cin >> a[i].x >> a[i].y;
	}
	auto vd0 = voronoi(a);
	std::cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	auto vd1 = negvoronoi(a);
	std::cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	db ans = 1e18, r = 0;
	ll x = 0, y = 0, z = 1;
	int is_line = 1;
	auto b = gethull(a);
	for(int i = 0;i < (int) b.size();++i)
		for(int j = 0;j < i;++j) {
			vec2 t = r90(b[j] - b[i]), negt = vec2{} - t;
			int A = findmax(t, b);
			int B = findmax(negt, b);
			db v = (b[A] - b[B]) % t / t.abs();
			v /= 2;
			if(v < ans) {
				ans = v;
				x = round(t.x * 2);
				y = round(t.y * 2);
				z = round(t % (b[A] + b[B]));
			}
		}

	for(int i = 0;i < n;++i) if(vd1[i].size()) {
		for(int j = 0;j < n;++j) {
			auto tmp = vd1[i];
			for(auto t : vd0[j]) {
				tmp = cut(tmp, t);
				if(!tmp.size()) break;
			}
			auto judge = [&](line A, line B) {
				if(fabs(A * B) <= 0.1) return ;
				vec2 X = A & B;
				if(X.abs() >= V) {
					X = {(ll) X.x, (ll) X.y};
				}
				db d1 = (X - a[i]).abs();
				db d0 = (X - a[j]).abs();
				for(int k = 0;k < n;++k) {
					d1 = std::max(d1, (X - a[k]).abs());
					d0 = std::min(d0, (X - a[k]).abs());
				}
				db val = std::abs((d1 - d0) / 2);
				if(val < ans) {
					ans = val;
					r = (d0 + d1) / 2;
					is_line = 0;
					if(X.abs() >= V) {
						x = X.x;
						y = X.y;
						z = 1;
					} else {
						std::tie(x, y, z) = A && B;
					}
				}
			};
			if(tmp.size()) {
				for(int k = 0;k < (int) tmp.size();++k) {
					line a = tmp[k], b = tmp[(k + 1) % tmp.size()];
					judge(a, b);
				}
			}
		}
	}
	std::cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	printf("%.10Lf\n", std::max(ans + 1e-7, ans * (1 + 1e-7)));
	if(is_line) {
		printf("L %lld %lld %lld\n", x, y, z);
	} else {
		printf("C %lld %lld %lld %.10Lf\n", x, y, z, r);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2 1
1 3
2 4
7 2

output:

0.2706907326
C 72 45 18 2.7706906326

result:

ok jury ans = 0.270690633, participant ans = 0.270690733

Test #2:

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

input:

7
26919 7739
85584 91359
47712 21058
13729 26355
16636 96528
88747 93023
46770 1150

output:

9663.8805638790
C 112674302524076 183554866947533 3011524769 50864.3320530346

result:

ok jury ans = 9663.879597491, participant ans = 9663.880563879

Test #3:

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

input:

10
756 624
252 208
504 416
378 312
203 287
329 391
0 0
707 703
126 104
581 599

output:

46.0591574880
L 1248 -1512 -90300

result:

ok jury ans = 46.059152882, participant ans = 46.059157488

Test #4:

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

input:

1
15782 63130

output:

0.0000001000
C -1000000000 -1000000000 1 1414269361.9797002531

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #5:

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

input:

2
94217 66974
75089 40029

output:

0.0000001000
L 53890 -38256 2515196786

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #6:

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

input:

3
48303 6057
77370 21547
87988 74434

output:

0.0000001000
C 109980206721647 155256378115679 2745587218 51159.5178463256

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #7:

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

input:

4
91497 34248
20062 67825
81300 76644
27657 65928

output:

3533.5717117199
C 8628232018140 6441360711045 156439050 40530.8532879950

result:

ok jury ans = 3533.571358363, participant ans = 3533.571711720

Test #8:

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

input:

5
69930 13744
97997 49343
74612 89749
36739 52364
89397 14014

output:

5337.8540635665
C 618235642032675 450340094908105 9189418290 36059.7905359099

result:

ok jury ans = 5337.853529781, participant ans = 5337.854063567

Test #9:

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

input:

6
24017 52829
277 30862
67924 91959
21473 63146
96602 58155
873 44434

output:

9102.8228650390
C 385087733514103 178655356183771 6184976998 54224.4493237426

result:

ok jury ans = 9102.821954757, participant ans = 9102.822865039

Test #10:

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

input:

7
2451 56672
42971 77140
61236 94170
81861 25235
68565 61883
16219 86220
16322 5864

output:

10266.4211481316
C 126350248388825 141147220029391 2945356662 39484.5660052495

result:

ok jury ans = 10266.420121490, participant ans = 10266.421148132

Test #11:

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

input:

8
21297 95757
45252 58658
94961 72033
66596 11671
64876 30371
66805 92765
94633 86321
40385 47610

output:

15105.3207717616
C 465051544188545 452234886264771 6714637102 40637.9512733325

result:

ok jury ans = 15105.319261230, participant ans = 15105.320771762

Test #12:

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

input:

9
99732 23947
23186 80590
12619 74244
75677 73760
36840 74512
6496 34550
8184 26365
6 6454
55215 18208

output:

14885.2331644417
C 528236147497509 544471010864505 11872813158 44542.5533644824

result:

ok jury ans = 14885.231675919, participant ans = 14885.233164442

Test #13:

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

input:

10
67694 99307
56012 50355
42446 60253
398 14855
82806 93134
53045 14189
19963 51406
72238 90783
58977 92553
91808 75523

output:

21890.6743118141
C 48293860224471 157269094149141 2072072122 46611.3258319037

result:

ok jury ans = 21890.672122747, participant ans = 21890.674311814

Test #14:

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

input:

50
28303 78635
98527 4836
99469 93880
46037 26886
31814 11072
82640 89089
80483 78420
65817 78003
4325 65401
87358 36627
69197 63160
8603 49295
15942 84649
58111 43187
59748 20332
26719 92486
4108 32640
60387 68724
43155 47327
9591 99815
37905 98234
25483 54545
89447 86614
63335 62433
60686 44416
15...

output:

27130.4302759467
C 208208852697721 201287291063801 3707918566 37991.6198990597

result:

ok jury ans = 27130.427562904, participant ans = 27130.430275947

Test #15:

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

input:

50
86917 20549
60266 58924
3312 36573
27556 20198
9678 20153
69075 96294
48970 53352
72362 91554
44370 89782
21855 61657
57607 89111
87444 40267
39146 58700
27668 65946
45465 14550
28873 59735
15851 10864
2791 66253
20744 34442
28637 44319
1253 6922
16147 51571
72072 39253
78169 46742
22183 97841
22...

output:

28626.3967399098
C 309328046815971 252437996644215 5477616186 39070.2042136055

result:

ok jury ans = 28626.393877270, participant ans = 28626.396739910

Test #16:

score: 0
Accepted
time: 2981ms
memory: 6364kb

input:

3000
92948 78658
99013 65575
62135 58049
73566 5036
62021 41092
18242 18337
69531 93648
48044 47267
90750 98807
54790 73639
70408 13307
68742 82075
21339 47233
75103 97053
10958 13262
52441 39682
55881 21527
36660 9741
10401 25304
66452 74105
21712 20753
6193 73558
64161 45507
38414 99590
87783 9105...

output:

33766.3170515402
C 31773882892491 31297645626819 636923746 35113.4576997247

result:

ok jury ans = 33766.313674909, participant ans = 33766.317051540

Test #17:

score: 0
Accepted
time: 2979ms
memory: 6268kb

input:

3000
27214 96226
85099 19662
65979 35983
30738 22695
64232 25826
80332 65955
38018 8993
54589 60818
30793 23188
13634 33910
69713 39258
47582 73047
93237 21284
20313 19811
85782 7480
54595 6931
43277 24097
38652 42511
63644 12419
85498 83369
9407 29441
96858 70585
82028 22493
77595 59552
49280 68829...

output:

34199.4158700128
C 2550123021178 2715323152220 52629791 35900.8543833831

result:

ok jury ans = 34199.412450072, participant ans = 34199.415870013

Test #18:

score: 0
Accepted
time: 2965ms
memory: 6144kb

input:

3000
37134 38141
82080 22442
5063 78677
12256 16007
66442 34908
66767 62266
6505 59579
96375 74369
11250 31503
48132 83287
93364 65208
26422 39673
5546 6228
65525 82983
20191 26045
81096 33767
90261 77975
16296 40040
30339 15599
4542 16980
32342 97718
22762 67611
64654 50785
68081 19514
35124 33147
...

output:

34115.5090554917
C 26326184364477 27446259085047 542331774 35250.4665977286

result:

ok jury ans = 34115.505643941, participant ans = 34115.509055492

Test #19:

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

input:

100
19268 48372
48595 53219
31920 44184
21912 55164
42130 54945
19984 48704
4648 55722
40500 43319
42508 53624
24054 54237
45679 45165
7169 51472
1871 45270
37289 57530
28573 49283
7029 49215
44885 51786
32613 49560
10985 57784
37606 46069
24510 55357
41305 49669
13344 48648
13718 54893
12753 47755
...

output:

7198.7038948399
C 472164776811 6197396390133 11182134 503708.2568178959

result:

ok jury ans = 7198.703174970, participant ans = 7198.703894840

Test #20:

score: 0
Accepted
time: 5ms
memory: 4008kb

input:

100
57704 46888
86842 42687
85439 36827
60194 50133
95958 37663
68574 48860
60804 40463
99285 30498
86514 35268
78568 36730
89913 36994
66635 41831
87563 41434
89624 40740
89642 30658
78771 38490
84061 35472
67029 45196
72874 38697
91088 32916
50673 46863
56910 44507
60477 44574
98348 35464
86335 34...

output:

5627.1858751221
C 6516701427555 19090335746163 468006 43038408.8105079697

result:

ok jury ans = 5627.185312404, participant ans = 5627.185875122

Test #21:

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

input:

100
36940 69135
2650 85030
40502 97427
94724 76410
30024 89470
88244 38884
31880 58708
84518 54289
43910 83402
84355 56828
80732 97217
30977 88024
18859 76936
55086 57274
20500 82287
22964 67111
93768 97769
29970 91772
36269 71348
70332 52328
27049 80960
6407 72600
40903 90864
53156 84794
91227 8100...

output:

21510.2249042180
C 57532907745009 82026291586889 1105113262 29068.1739099410

result:

ok jury ans = 21510.222753196, participant ans = 21510.224904218

Test #22:

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

input:

100
68023 74737
73738 65097
49745 43105
96797 62905
53809 26796
84698 70442
67067 6393
71539 36404
67660 34832
66833 80545
62325 62494
75928 86937
84157 27616
73589 57334
76497 11703
56575 80314
90841 53175
64247 83001
49283 16735
62540 18314
81676 5039
57097 39741
70209 73607
75279 25719
62717 3555...

output:

23322.4848409453
C 69143500227835 46998187043303 931564450 30234.8020532842

result:

ok jury ans = 23322.482508697, participant ans = 23322.484840945

Test #23:

score: 0
Accepted
time: 3502ms
memory: 5140kb

input:

1100
0 4969
2 4945
4 4929
6 4916
8 4905
10 4895
13 4881
18 4862
28 4829
35 4810
40 4797
46 4783
50 4774
55 4763
71 4731
84 4708
90 4698
103 4677
119 4653
133 4634
150 4611
161 4597
188 4565
205 4546
216 4534
241 4508
244 4505
275 4475
292 4459
304 4448
321 4433
342 4415
373 4389
388 4377
402 4366
42...

output:

4999.4940611706
C 24754455 256418910 495 513019.4581895811

result:

ok jury ans = 4999.493561221, participant ans = 4999.494061171

Test #24:

score: 0
Accepted
time: 3507ms
memory: 5108kb

input:

1100
0 4971
3 4937
4 4930
8 4905
13 4881
21 4853
27 4833
31 4821
39 4800
43 4790
51 4772
57 4759
66 4741
74 4726
92 4695
98 4685
103 4677
120 4652
127 4642
157 4602
176 4579
213 4537
236 4513
247 4502
278 4472
313 4440
330 4425
337 4419
368 4393
389 4376
425 4348
449 4330
464 4319
519 4280
547 4261
...

output:

4999.4907312315
C 148050000 -1463645001 2961 499308.1422842729

result:

ok jury ans = 4999.490231282, participant ans = 4999.490731231

Test #25:

score: 0
Accepted
time: 3501ms
memory: 5128kb

input:

1100
0 49014
3 48003
5 47564
7 47180
11 46554
13 46268
14 46143
16 45899
19 45542
21 45325
22 45222
25 44916
28 44630
32 44276
37 43851
39 43692
42 43457
48 43018
50 42879
56 42473
59 42278
67 41783
73 41430
81 40983
87 40672
90 40517
94 40315
101 39962
107 39666
117 39201
124 38891
128 38716
131 38...

output:

4999.4630975397
C -2064927645 198321813 3966 525657.9066648149

result:

ok jury ans = 4999.462597593, participant ans = 4999.463097540

Test #26:

score: 0
Accepted
time: 3518ms
memory: 5032kb

input:

1100
0 49100
1 48615
2 48269
4 47785
5 47555
7 47179
8 47007
9 46847
11 46538
17 45769
20 45423
21 45322
25 44928
26 44831
32 44266
34 44097
38 43767
47 43088
52 42742
54 42608
64 41967
69 41663
74 41376
80 41042
88 40609
99 40054
105 39763
110 39524
117 39207
124 38891
131 38587
133 38503
142 38129...

output:

4999.4504115404
C 2081583987 197400000 3948 522251.6415894678

result:

ok jury ans = 4999.449911595, participant ans = 4999.450411540

Test #27:

score: 0
Accepted
time: 4843ms
memory: 6012kb

input:

2000
0 49693
2 49452
3 49370
4 49295
6 49165
7 49111
9 49008
10 48958
18 48630
23 48451
29 48268
31 48212
34 48129
36 48078
42 47927
50 47745
53 47677
54 47655
60 47530
74 47263
81 47140
85 47073
101 46808
108 46701
118 46552
137 46290
140 46249
145 46182
157 46028
165 45929
170 45870
188 45659
197 ...

output:

0.3333004765
C 59694650987257 59694751028433 1193905094 50000.4169348118

result:

ok jury ans = 0.333300376, participant ans = 0.333300476

Test #28:

score: 0
Accepted
time: 4861ms
memory: 5892kb

input:

2000
0 49712
1 49581
2 49460
3 49377
6 49164
12 48860
17 48664
19 48586
22 48484
23 48452
35 48106
39 48003
43 47905
47 47810
56 47614
63 47471
69 47355
80 47158
84 47089
102 46793
126 46438
148 46144
161 45979
176 45797
200 45521
204 45477
217 45336
233 45170
246 45036
252 44976
267 44830
280 44706...

output:

0.3232332879
C 592398306391017 592398378814181 11848083266 50000.3722029959

result:

ok jury ans = 0.323233188, participant ans = 0.323233288

Test #29:

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

input:

400
35034 65376
87242 59352
480 69363
82874 59856
81938 59964
85422 59562
68886 61470
13142 67902
48528 63819
33032 65607
64648 61959
71044 61221
81808 59979
19746 67140
48814 63786
64778 61944
20552 67047
26870 66318
76686 60570
60982 62382
71954 61116
50270 63618
41846 64590
9268 68349
81886 59970...

output:

0.0000001000
L -22836 -197912 -13738731336

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #30:

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

input:

400
768 30365
6873 42982
8313 45958
25308 81081
7563 44408
18408 66821
15138 60063
468 29745
33978 98999
648 30117
9903 49244
28053 86754
1278 31419
22248 74757
11073 51662
2643 34240
738 30303
3483 35976
978 30799
29778 90319
5403 39944
23568 77485
12948 55537
16818 63535
25773 82042
26328 83189
24...

output:

0.0000001000
L 142290 -68850 -1981351530

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #31:

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

input:

400
57291 43259
59253 44458
25683 23943
3651 10479
21795 21567
88971 62619
50343 39013
51423 39673
24873 23448
23667 22711
36717 30686
16089 18080
60873 45448
50145 38892
39255 32237
66525 48902
11085 15022
46707 36791
48705 38012
70719 51465
34593 29388
66489 48880
51585 39772
80655 57537
52971 406...

output:

0.0000001000
L 121264 -198432 -1636634064

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #32:

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

input:

200
96600 26052
60564 34515
1560 48372
37200 40002
79572 30051
11856 45954
30072 41676
24132 43071
22152 43536
93036 26889
13044 45675
4332 47721
49476 37119
24528 42978
47100 37677
52644 36375
15420 45117
42744 38700
98184 25680
51852 36561
34824 40560
32844 41025
23340 43257
53832 36096
11460 4604...

output:

0.0000001000
L -46500 -198000 -9650196000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #33:

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

input:

200
10835 95282
69400 59038
23555 87410
55885 67402
40250 77078
19315 90034
30710 82982
55620 67566
6860 97742
42370 75766
52175 69698
14280 93150
3415 99874
41045 76586
45285 73962
18520 90526
80265 52314
81060 51822
76025 54938
99345 40506
29385 83802
60655 64450
4475 99218
82915 50674
12955 93970...

output:

0.0000001000
L -118736 -191860 -19567309080

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #34:

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

input:

200
73206 52053
73394 52147
59576 45238
58636 44768
79504 55202
15020 22960
40212 35556
49706 40303
20190 25545
6842 18871
29120 30010
91724 61312
78188 54544
2048 16474
98868 64884
68224 49562
40400 35650
75932 53416
61644 46272
46792 38846
69446 50173
72548 51724
42562 36731
78094 54497
15866 2338...

output:

0.0000001000
L 99452 -198904 -3073066800

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #35:

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

input:

28
53013 50869
48913 47069
51113 47069
49776 46878
48333 47359
53129 50231
46897 49757
51693 52629
50013 53119
46897 50231
51693 47359
49138 52994
48138 52494
49138 46994
47013 50869
47378 48314
51888 52494
50013 46869
52513 51869
47088 51094
52648 51674
50250 46878
52938 48894
51113 52919
48333 526...

output:

0.0000001000
C 3488156685 3486831530 69745 3125.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #36:

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

input:

25
35007 54374
50007 34374
40632 37499
61760 60295
65007 45624
65587 51184
55507 35374
35382 44499
60303 38246
58407 36824
39711 61752
63182 41599
55507 64624
44507 64624
59382 62499
63182 58399
36832 41599
35382 55499
37507 59374
37507 40624
34427 48814
62507 40624
64632 44499
34427 51184
65632 49999

output:

0.0000001000
C 13595653125 13593478125 271875 15625.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #37:

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

input:

90
55302 18378
62323 79561
41418 80856
61659 20133
18786 57240
81321 56745
42110 81040
62918 20656
63570 79010
81115 57637
22185 34065
18939 42093
27754 73048
20418 62306
19177 41209
18675 56745
53755 81805
50714 82018
34918 21706
28422 26288
52275 81945
46043 18181
66267 77589
25874 28888
22651 332...

output:

0.0000001000
C 2486150550 2485305225 49725 32045.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #38:

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

input:

59
44569 51035
52040 44866
44991 47659
44505 49387
47116 45284
49384 55490
46496 54274
53948 53860
54553 46875
54416 46684
45576 53314
44641 51359
47191 45239
45911 53719
44863 52043
53716 54084
47116 54714
49384 44508
47871 55099
55351 48639
45439 53123
46528 54300
44912 47836
54756 47194
54711 528...

output:

0.0000001000
C 48446124 48449031 969 5525.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #39:

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

input:

44
48340 47355
48920 47065
52520 48115
50257 46874
47385 48310
53145 49990
51895 52490
50020 46865
51700 52625
51895 47490
52655 51670
49783 53106
46904 49753
47520 48115
52520 51865
46895 49990
48145 47490
50895 46990
48340 52625
53136 49753
49145 52990
51120 52915
52655 48310
48920 52915
47095 488...

output:

0.0000001000
C 543967500 543641250 10875 3125.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #40:

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

input:

39
65010 45631
60306 61759
55510 64631
38257 60302
51195 34426
48825 34426
44510 64631
39714 61759
65590 51191
50010 65631
65010 54381
64635 44506
34385 50006
62510 40631
37510 59381
45635 35006
36835 58406
62510 59381
34430 51191
64635 55506
59385 62506
55510 35381
35385 44506
58410 63181
51195 655...

output:

0.0000001000
C 13596468750 13595381250 271875 15625.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #41:

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

input:

280
51368 17965
47728 18017
46050 18181
67056 22849
65085 21706
20425 62306
77613 66250
31714 23669
77936 65689
38344 79829
74800 70281
17989 48618
81217 42722
75394 69533
67258 76985
19624 60173
18402 44677
79330 62901
20085 61456
58777 80802
71098 25857
49289 82018
57264 18769
55309 18378
81673 54...

output:

0.0000001000
C 1355885575 1355234815 27115 32045.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #42:

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

input:

158
48683 44641
45288 47126
44595 51137
46535 45705
46688 45586
48683 55371
55494 49394
44478 50006
44870 47962
55523 49771
44648 48646
45702 53474
52343 45001
54423 46691
45128 47406
45583 46691
53471 54307
52343 55011
44503 50531
48967 44579
52047 44873
47403 45131
49478 55506
49391 44515
48456 55...

output:

0.0000001000
C 4250255 4250510 85 5525.0000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000100

Test #43:

score: 0
Accepted
time: 2520ms
memory: 5888kb

input:

2780
43634 9527
30398 29204
30402 29237
30411 29218
43626 9478
43706 9456
30436 29192
43649 9550
30382 29179
43709 9527
43644 9465
30385 29239
30448 29182
30419 29238
30426 29245
30377 29168
30413 29171
43639 9549
30430 29151
30379 29219
43654 9509
30368 29234
30378 29158
43698 9503
30452 29203
3043...

output:

56.5707746238
C 132600736053 61960644369 4893138 16861.9839128918

result:

ok jury ans = 56.570768967, participant ans = 56.570774624

Test #44:

score: 0
Accepted
time: 2991ms
memory: 6336kb

input:

3000
35274 18457
11468 6660
35219 17956
11137 6573
10999 6016
11248 5905
14689 20868
35639 18485
35245 18515
15136 21029
35759 18417
14823 20861
14863 20861
35962 17808
15097 20761
14788 20691
14913 20639
11652 6405
11102 6301
35436 18067
11362 5883
15626 20857
14655 20210
15325 20600
11152 5906
151...

output:

680.7867171142
C 3583586402192 1521376357996 147719843 13757.3656778892

result:

ok jury ans = 680.786649035, participant ans = 680.786717114

Test #45:

score: 0
Accepted
time: 2995ms
memory: 6264kb

input:

3000
49015 39407
48775 38034
51749 41060
25465 42992
50182 26399
23818 37501
28057 40952
48000 19119
55225 33795
23212 44126
46354 25090
46239 16846
20113 36416
45422 20320
47046 26512
20737 37247
51122 23833
51121 37396
46767 23713
52096 26148
26144 37564
23373 37475
47978 19025
20708 39100
46180 3...

output:

6776.1708983764
C 25367266935387 22545620459651 686169826 15449.8323170580

result:

ok jury ans = 6776.170220759, participant ans = 6776.170898376

Test #46:

score: 0
Accepted
time: 2390ms
memory: 5836kb

input:

2703
21451 22964
31281 37761
38355 54004
21454 22989
21446 22970
38347 54017
38352 54070
21501 23057
21465 22985
38301 54091
21444 23011
38371 54039
31329 37688
31257 37761
31276 37704
31294 37721
38289 54104
21488 23004
19204 31330
19213 31380
21506 23052
38355 54060
19191 31338
21447 23053
19183 3...

output:

3154.4021281990
C 6353697826169 -1410537489224 58891076 101424.9388574769

result:

ok jury ans = 3154.401812759, participant ans = 3154.402128199

Test #47:

score: 0
Accepted
time: 2610ms
memory: 5996kb

input:

2799
28393 41202
39431 13585
31349 6556
12466 24297
12973 24676
28487 41308
39814 14348
13030 24327
39711 14057
28679 41157
39977 14243
31445 6502
29144 41122
12518 24438
31211 6358
12811 24697
39956 14249
40068 14345
40256 14282
39945 13956
13137 24946
30832 6525
30894 6076
13246 24925
30714 5950
3...

output:

1704.5736587756
C 12716667131122 10735805249544 454958077 16401.7926105987

result:

ok jury ans = 1704.573488318, participant ans = 1704.573658776

Test #48:

score: 0
Accepted
time: 2602ms
memory: 6292kb

input:

2800
55731 53447
40124 50201
40428 50643
52854 59719
57067 55144
57183 54026
39429 51201
57370 54659
40024 50146
39446 50086
57377 54664
52666 58913
40554 49812
46784 4508
56067 54286
52798 58973
57065 54442
55746 53579
39954 51325
47274 3622
48433 3844
56740 53575
46797 3168
53209 59765
40612 51268...

output:

3756.8387489700
C 21708750623835 12736010740605 403728310 25646.0819250304

result:

ok jury ans = 3756.838373286, participant ans = 3756.838748970

Test #49:

score: 0
Accepted
time: 2072ms
memory: 6000kb

input:

2497
41752 19228
44525 2912
31252 11042
43448 9139
16052 48892
25294 21318
40433 55158
45875 33198
14671 5656
13591 55454
16900 36294
43434 9116
44473 2873
32465 30941
34701 17016
47338 21250
36066 15180
695 13204
36065 15216
24148 48045
52176 11474
49389 29020
43473 9087
43628 13873
14622 5678
4343...

output:

15773.4122014525
C 28125777914663 19145054169293 788111182 23112.2010318383

result:

ok jury ans = 15773.410624111, participant ans = 15773.412201453

Test #50:

score: 0
Accepted
time: 2095ms
memory: 5872kb

input:

2500
36288 48418
10406 37910
27385 59996
8715 8497
44976 59654
45486 60162
15058 51485
6089 9925
11079 21352
45593 59945
56627 37153
42206 1655
50021 40633
14338 15068
13418 28825
33262 54391
26646 31380
44200 9953
26929 31185
14930 51422
42013 1709
18849 54764
33170 54798
50552 16735
41829 1600
542...

output:

13332.3228797824
C 38019659115021 31234682051251 1108694862 20884.7072467430

result:

ok jury ans = 13332.321546550, participant ans = 13332.322879782

Test #51:

score: 0
Accepted
time: 2118ms
memory: 6084kb

input:

2500
37307 45325
30558 13213
18676 59524
4464 3353
7228 944
31560 24904
32926 28522
20110 57209
17218 5785
32016 25519
60094 35007
5578 58099
45953 50831
4027 56287
47555 51218
26967 31918
16868 54274
7238 2218
34001 26346
56705 56064
33430 26032
14054 29927
22152 2878
34696 58986
46690 52327
31967 ...

output:

18906.2601728404
C 6669485810459 9368540661114 260249774 22150.4243472274

result:

ok jury ans = 18906.258282215, participant ans = 18906.260172840

Test #52:

score: 0
Accepted
time: 9417ms
memory: 6476kb

input:

3000
73303 38669
61787 30119
28049 56995
98407 37479
1203 60906
26539 29928
56594 40485
54107 168
97609 34723
35444 26264
86161 84530
6875 24695
66842 31381
94567 27333
82518 87981
18733 89018
78681 9043
53685 135
4015 69633
99472 57247
18190 11422
25167 55964
94291 73201
42604 72280
96575 31813
867...

output:

24672.3849887539
C 228388041439 229519407329 4603054 25734.8103310735

result:

ok jury ans = 24672.382521516, participant ans = 24672.384988754

Test #53:

score: 0
Accepted
time: 9417ms
memory: 6184kb

input:

2999
33802 51428
36854 98241
99999 50305
83792 86852
29765 34346
70644 4460
76692 7720
74464 29679
30294 4046
97998 35993
37627 98445
44737 99722
33617 97240
67493 3159
17316 12160
56344 52247
36386 98111
79104 90656
14850 85560
56467 64975
78089 91364
96169 69194
28711 72799
32584 96869
1406 61777
...

output:

24299.6121370401
C 37795470837 37848540378 756492 25750.7724542612

result:

ok jury ans = 24299.609707079, participant ans = 24299.612137040

Test #54:

score: 0
Accepted
time: 9358ms
memory: 6460kb

input:

2998
57800 54626
67386 52261
32212 3270
29422 37910
93120 75311
34783 2371
28029 73636
94999 28203
55169 267
92587 23801
61912 98560
14365 85074
12244 82780
37441 47562
98386 62600
25909 93814
28892 72448
57058 99499
40431 36604
32157 54062
62520 1592
93214 75150
44128 68875
99871 53587
21287 90934
...

output:

24853.8284143182
C 268708741215 281195383023 5445934 26908.6994028311

result:

ok jury ans = 24853.825928936, participant ans = 24853.828414318

Test #55:

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

input:

68
46990 49106
47004 49107
48904 52907
52642 51698
52932 51118
51884 52500
53004 49107
48886 47073
53125 50237
48115 47481
47369 51662
49115 46981
48306 52633
46879 49982
46986 49123
47507 51893
48324 52617
49134 47000
50009 53125
49770 53134
52915 51081
51689 52635
48909 52925
52990 49106
52625 483...

output:

19.5409475361
C 108503545348 108502738740 2170091 3125.7152638865

result:

ok jury ans = 19.540945582, participant ans = 19.540947536

Test #56:

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

input:

23
38248 60286
44515 64609
35385 55488
65001 45615
48825 34408
35010 45613
35005 45617
34421 48805
64989 54384
65585 51177
48816 65570
41605 63167
62515 40609
55510 64613
37505 59367
60285 61762
38236 60305
48825 65568
35001 45615
49989 65634
40635 62488
38252 39696
58405 36817

output:

15.4942455588
C 40125332414537 40120154937573 802546478 15627.7320082075

result:

ok jury ans = 15.494244009, participant ans = 15.494245559

Test #57:

score: 0
Accepted
time: 1434ms
memory: 5236kb

input:

1605
81204 42754
74123 71104
22988 67266
47618 81966
26813 27911
27900 73221
75200 69811
72092 73218
32746 77015
17975 50699
57880 81072
75654 69238
22988 32760
24364 30789
20667 62933
61493 79931
60191 80392
31727 23699
81824 53773
67051 77148
17955 50729
20970 63583
68290 76323
45117 81679
71000 7...

output:

18.1903929706
C 57667843169867 57662452599683 1153263986 32045.0000004016

result:

ok jury ans = 18.190391152, participant ans = 18.190392971

Test #58:

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

input:

357
50527 44498
51558 55292
54269 46511
52046 55131
52157 44906
51126 44574
53954 46137
45591 53303
50623 44497
44587 51113
44503 50602
55349 48630
54754 52795
47950 44857
48634 55366
51354 55345
46042 53851
54877 47398
48691 55353
45280 47102
55095 52107
48464 55292
46511 54263
46526 54291
50519 55...

output:

15.0792423979
C 1492190974947 1492131356802 29844633 5525.0052556346

result:

ok jury ans = 15.079240890, participant ans = 15.079242398

Test #59:

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

input:

41
53119 50227
49765 53098
48131 47480
46878 50017
53126 50017
49137 47013
50249 53129
49779 46891
47503 51892
46887 50254
52941 48907
52503 48115
52637 48302
48332 52648
52503 51892
53131 49980
46896 50250
53127 49982
49128 52990
53118 50219
51680 52643
53003 50865
50881 52980
48141 52507
46885 502...

output:

16.0954852486
C 387549078910 387514171820 7750395 3123.2159656955

result:

ok jury ans = 16.095483639, participant ans = 16.095485249

Test #60:

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

input:

88
55496 64617
40610 37493
59381 37504
37496 40617
35360 44493
59370 37505
48800 65573
36810 58393
51188 34401
48799 65578
36819 58412
50006 34379
34994 45637
45609 64998
44494 64637
65574 48827
65565 51178
65609 49998
40610 62493
61749 60303
63160 58393
35006 54379
63178 58381
34996 45617
60280 617...

output:

16.0919054766
C 1252567647525 1252499197400 25051535 15625.0217932207

result:

ok jury ans = 16.091903867, participant ans = 16.091905477

Test #61:

score: 0
Accepted
time: 1070ms
memory: 5016kb

input:

1404
81964 47735
32949 77144
82007 51346
30448 24609
77139 32948
80821 41240
30764 24360
53955 81812
65080 78273
67256 23010
72244 26931
22177 65911
65916 77825
75200 69807
52391 18041
39811 80395
37070 20670
78278 65094
77132 32947
74785 29695
38339 20150
75200 69793
31712 76326
37080 20673
30224 7...

output:

17.5745013694
C 105979996140607 105967510967974 2119501206 32045.0000009696

result:

ok jury ans = 17.574499612, participant ans = 17.574501369

Test #62:

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

input:

441
51021 44577
55395 48885
55540 49745
46124 53956
53939 53877
52790 54764
52792 54776
53129 54548
46513 54291
53730 54089
54745 47199
51116 55412
54562 46867
54733 52881
53874 46064
52157 44931
46889 54573
49408 44489
46126 53968
53485 54279
51370 55359
53520 54255
54575 53125
46679 45595
52890 45...

output:

24.4056306463
C 734431465430 734348881965 14687210 5525.0662616621

result:

ok jury ans = 24.405628206, participant ans = 24.405630646

Test #63:

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

input:

379
56619 21936
4278 1797
47495 21656
59215 2714
65257 9809
59962 20948
20013 20448
6638 580
62473 4831
65009 15093
774 6139
51 11015
52347 1850
63354 5809
48616 1686
23198 20588
64595 7842
59711 21069
790 6101
55987 2010
3803 17847
65429 10813
9436 14
973 14303
65181 9494
6309 19293
24472 20644
654...

output:

9999.9823735435
L -3960 90090 861140610

result:

ok jury ans = 9999.981373545, participant ans = 9999.982373544

Test #64:

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

input:

400
502 1867
782 1976
757 1970
2121 2244
876 7
5828 945
745 1967
9239 3173
9377 2980
13 834
3683 516
9495 2402
1598 99
4461 2712
7671 3354
9490 2359
8061 3432
123 1482
6816 3183
7551 3330
289 295
9479 2296
8016 3423
319 1733
2093 198
585 89
3338 447
390 206
3938 567
8678 1515
5751 2970
8912 3411
114...

output:

1000.3885053787
L 3006 -15030 -12017988

result:

ok jury ans = 1000.388405340, participant ans = 1000.388505379

Test #65:

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

input:

320
5261 14992
67720 6648
23 9511
67378 7413
3334 14713
9 9685
1124 13158
65775 839
42863 11753
1337 6594
67688 6737
3095 14622
66015 1010
67821 6323
66269 1215
64660 282
67570 7027
14849 14168
2206 5851
612 12397
63725 51
3024 5405
4000 14898
3064 5388
38165 12158
63171 1
67576 2984
1698 13754
3765...

output:

5000.1792928082
L -10010 -116116 -1211015806

result:

ok jury ans = 5000.178792790, participant ans = 5000.179292808

Test #66:

score: 0
Accepted
time: 1564ms
memory: 5568kb

input:

2028
7637 2508
20456 6990
9329 3072
24521 8136
29381 9756
13253 4380
25061 8316
35180 11898
4757 1548
29345 9744
7241 2376
19124 6546
2996 1170
15308 5274
5372 1962
20129 6672
34928 11814
7061 2316
8825 2904
11744 4086
28985 9624
34820 11778
26645 8844
13541 4476
7928 2814
35576 12030
29273 9720
634...

output:

99.1374145600
L -23976 71928 4807188

result:

ok jury ans = 99.137404646, participant ans = 99.137414560

Test #67:

score: 0
Accepted
time: 1398ms
memory: 5476kb

input:

1998
1348 31328
2450 31791
39508 5888
35762 9583
18292 20032
37876 6976
6388 27968
31204 11424
48889 807
25588 15168
26500 14560
4706 30287
4708 29088
45604 1824
15794 22895
37346 8527
18484 19904
7252 27392
28466 14447
19972 18912
29330 13871
43636 3136
37828 7008
42004 4224
38404 6624
38546 7727
9...

output:

498.2595010853
L -64064 -96096 -3154399248

result:

ok jury ans = 498.259451259, participant ans = 498.259501085