QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#251214 | #7568. Keychain | ucup-team1209 | AC ✓ | 9344ms | 5984kb | C++20 | 7.3kb | 2023-11-14 13:55:33 | 2023-11-14 13:55:33 |
Judging History
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, {
{1, 0, V}, {-1, 1, 2 * V},
{-1, -1, 2 * 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, {
{1, 0, V}, {-1, 1, 2 * V},
{-1, -1, 2 * 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);
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
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: 3856kb
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: 3728kb
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: 1ms
memory: 3736kb
input:
1 15782 63130
output:
0.0000001000 C -1000000000 -3000000000 1 3162342541.2555276225
result:
ok jury ans = 0.000000000, participant ans = 0.000000100
Test #5:
score: 0
Accepted
time: 1ms
memory: 3900kb
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: 1ms
memory: 3744kb
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: 1ms
memory: 3908kb
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: 3708kb
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: 1ms
memory: 3744kb
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: 3840kb
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: 3908kb
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: 1ms
memory: 3744kb
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: 0ms
memory: 3904kb
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: 3828kb
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: 3816kb
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: 2969ms
memory: 5832kb
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: 2931ms
memory: 5788kb
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: 2909ms
memory: 5768kb
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: 3852kb
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: 3916kb
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: 3964kb
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: 3788kb
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: 3494ms
memory: 4772kb
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: 3483ms
memory: 4876kb
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: 3473ms
memory: 4876kb
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: 3481ms
memory: 4868kb
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: 4818ms
memory: 5412kb
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: 4825ms
memory: 5512kb
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: 37ms
memory: 3908kb
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: 3952kb
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: 3936kb
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: 4008kb
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: 3928kb
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: 3952kb
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: 2ms
memory: 3756kb
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: 1ms
memory: 3692kb
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: 8ms
memory: 3896kb
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: 3780kb
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: 2ms
memory: 3824kb
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: 3ms
memory: 3932kb
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: 3912kb
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: 23ms
memory: 3944kb
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: 2475ms
memory: 5696kb
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: 2965ms
memory: 5880kb
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: 2935ms
memory: 5788kb
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: 2351ms
memory: 5656kb
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: 2578ms
memory: 5644kb
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: 2564ms
memory: 5756kb
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: 2031ms
memory: 5444kb
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: 2065ms
memory: 5504kb
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: 2116ms
memory: 5456kb
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: 9266ms
memory: 5924kb
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: 9299ms
memory: 5860kb
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: 9344ms
memory: 5984kb
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: 3904kb
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: 3920kb
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: 1416ms
memory: 4892kb
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: 86ms
memory: 4140kb
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: 3940kb
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: 7ms
memory: 3968kb
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: 1059ms
memory: 4836kb
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: 116ms
memory: 4036kb
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: 233ms
memory: 4148kb
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: 197ms
memory: 4164kb
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: 174ms
memory: 4176kb
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: 1569ms
memory: 5132kb
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: 1368ms
memory: 5212kb
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