QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305905 | #6118. Eartheart | ckiseki | AC ✓ | 216ms | 24188kb | C++20 | 5.9kb | 2024-01-16 06:01:58 | 2024-01-16 06:01:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace {
using llf = long double;
using PTF = complex<llf>;
const llf eps = 1e-9;
int sgn(llf x) {
if (abs(x) < eps)
return 0;
return (x > 0) - (x < 0);
}
llf cross(PTF a, PTF b) {
return imag(conj(a) * b);
}
llf dot(PTF a, PTF b) {
return real(conj(a) * b);
}
PTF project(PTF p, PTF q) {
return dot(p, q) * q / dot(q, q);
}
struct L {
PTF st, ed, dir;
L(PTF s, PTF e)
: st(s), ed(e), dir(e - s) {}
static bool valid(llf, llf) { return true; }
vector<PTF> ends() { return {}; }
};
struct S {
PTF st, dir;
S(PTF s, PTF e) : st(s), dir(e - s) {}
static bool valid(llf p, llf q) {
if (sgn(q) < 0) q = -q, p = -p;
return 0 <= p and p <= q;
}
vector<PTF> ends() { return {}; }
};
template <typename T> bool isInter(T A, PTF P) {
if (abs(A.dir) < eps) return abs(P - A.st) < eps;
return sgn(cross(P - A.st, A.dir)) == 0
and T::valid(dot(P - A.st, A.dir), norm(A.dir));
}
template <typename U, typename V>
bool isInter(U A, V B) {
if (sgn(cross(A.dir, B.dir)) == 0) {
return false;
}
PTF D = B.st - A.st;
llf C = cross(A.dir, B.dir);
return U::valid(cross(D, B.dir), C) and V::valid(cross(D, A.dir), C);
}
template <typename U, typename V>
PTF intersect(const U &A, const V &B) {
llf t = cross(B.st - A.st, B.dir) / cross(A.dir, B.dir);
return A.st + t * A.dir;
}
vector<PTF> interCircle(const L &l, const PTF &c, const llf r) {
PTF ft = l.st + project(c - l.st, l.dir);
llf dis = abs(c - ft);
if (abs(dis - r) < eps) {
return {ft};
}
if (dis > r + eps) return {};
// cerr << "here " << l.dir << ' ' << ft << ' ' << r*r-dis*dis << endl;
PTF vec = l.dir * sqrt(max<llf>(0, r * r - dis * dis)) / abs(l.dir);
return {ft + vec, ft - vec};
};
optional<pair<llf, llf>> sausageBorder(PTF p1, PTF p2, llf d) {
if (sgn(imag(p1 - p2)) == 0) {
if (abs(imag(p1)) + eps < d) {
return minmax(real(p1), real(p2));
}
return {};
}
if (sgn(real(p1 - p2)) == 0) {
pair<llf, llf> r = minmax(imag(p1), imag(p2));
if (r.first + eps < 0 and eps < r.second)
return pair{real(p1) - d, real(p1) + d};
return {};
}
auto v = p1 - p2;
v = {-imag(v), real(v)};
v *= d / abs(v);
auto s1 = S(p1 - v, p2 - v);
auto s2 = S(p1 + v, p2 + v);
auto s3 = S(p1 - v, p1 + v);
auto s4 = S(p2 - v, p2 + v);
const L xl = L({0, 0}, {1, 0});
vector<PTF> vs;
for (auto s : vector{s1, s2, s3, s4}) {
if (isInter(xl, s))
vs.push_back(intersect(xl, s));
}
for (auto p : {p1 - v, p1 + v, p2 - v, p2 + v}) {
if (sgn(imag(p)) == 0)
vs.push_back(p);
}
if (vs.size() == 2)
return minmax(real(vs[0]), real(vs[1]));
assert (vs.size() < 2);
return {};
}
optional<pair<llf, llf>> circleBorder(PTF p1, llf d) {
auto v = interCircle(L({0, 0}, {1, 0}), p1, d);
if (v.size() != 2) return {};
return minmax(real(v[0]), real(v[1]));
}
optional<pair<llf, llf>> sausage_inter(PTF p1, PTF p2, llf d) {
optional<pair<llf, llf>> ans = {};
auto upd = [&ans](optional<pair<llf, llf>> x) {
if (not ans) ans = x;
else {
ans->first = min(ans->first, x->first);
ans->second = max(ans->second, x->second);
}
};
if (auto x = circleBorder(p1, d))
upd(x);
if (auto x = circleBorder(p2, d))
upd(x);
if (auto x = sausageBorder(p1, p2, d))
upd(x);
return ans;
}
} // namespace
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, r;
cin >> n >> r;
vector<PTF> pt(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
pt[i] = {x, y};
}
vector<pair<llf, llf>> segs;
for (int i = 0; i < n; i++) {
if (auto x = sausage_inter(pt[i], pt[(i + 1) % n], r)) {
cerr << "sausage seg " << x->first << ' ' << x->second << endl;
segs.emplace_back(x->first, x->second);
}
}
L xaxis_shifted(PTF{0, 0.5}, PTF{1, 0.5});
vector<llf> xs;
for (int i = 0; i < n; i++) {
S seg(pt[i], pt[(i + 1) % n]);
if (isInter(xaxis_shifted, seg)) {
auto ip = intersect(xaxis_shifted, seg);
// cerr << "ip = " << ip << endl;
llf x = real(ip);
xs.push_back(x);
}
}
assert (xs.size() % 2 == 0);
sort(xs.begin(), xs.end());
vector<tuple<llf,int,int>> evt;
for (auto [l, r]: segs) {
evt.emplace_back(l, 0, 1);
evt.emplace_back(r, 0, -1);
}
llf D = sqrt(1LL * r * r - 0.5 * 0.5);
// cerr << "D = " << D << endl;
for (int i = 0; i + 1 < xs.size(); i += 2) {
llf A = xs[i], B = xs[i + 1];
if (A + D <= B - D) {
llf L = A + D;
llf R = B - D;
// segs.emplace_back(A + r, B - r);
evt.emplace_back(L, 1, 0);
evt.emplace_back(R, -1, 0);
// cerr << "other seg " << L << ' ' << R << endl;
}
}
sort(evt.begin(), evt.end());
int cnt = 0;
int cnt2 = 0;
llf ans = 0;
for (int i = 0, j = 0; i < evt.size(); i = j) {
for (j = i; j < evt.size(); j++) {
if (get<0>(evt[j]) != get<0>(evt[i]))
break;
auto [_, a, b] = evt[j];
cnt += a;
cnt2 += b;
}
if (cnt > 0 && cnt2 == 0) {
assert (j != evt.size());
ans += get<0>(evt[j]) - get<0>(evt[i]);
}
}
cout << fixed << setprecision(20);
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3992kb
input:
4 5 -5 -5 5 -5 5 5 -5 5
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
4 5 -10 -10 10 -10 10 10 -10 10
output:
10.00000000000000000000
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
9 10 -100 -80 -90 130 -30 150 0 160 100 130 120 90 110 -60 80 -100 0 -120
output:
190.15694715649966195503
result:
ok found '190.15695', expected '190.15695', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
457 414687 -996315 -725321 -986403 -603614 -984900 -99226 -943685 -319681 -985352 -704158 -984699 -905259 -969935 -927143 -465900 -963727 -310171 -992145 -453426 -949729 -643489 -909695 -709791 -884030 -787622 -849046 -526296 -903166 -408863 -906869 -263787 -933392 -473870 -789072 -593393 -759966 -6...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 4184kb
input:
3157 635592 -998983 -17775 -993005 314040 -992532 -397616 -989247 708857 -985292 589314 -982046 726451 -979965 687632 -985621 240199 -978188 782690 -976339 41585 -981782 -274061 -974948 -410150 -980813 -585511 -980789 -865528 -981492 -862416 -984939 -322700 -984251 -496171 -985237 -472502 -991879 -4...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
1105 296370 -995471 952274 -991091 -838912 -968716 -981056 -955777 -928445 -879545 -975529 -834750 -968694 -825703 -878252 -787229 -998682 -764718 -954650 -732902 -919340 -610938 -966507 -267412 -971184 -68946 -980880 -178705 -973066 -291779 -953553 -347594 -912646 -338352 -904672 -270551 -821414 -1...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
179 22982 -998218 -375932 -924871 -833274 -965464 -861372 -304042 -941903 46407 -942280 576051 -973956 150160 -901679 604511 -911920 778636 -915852 -865584 -871767 -768265 -792995 -593904 -801716 -31277 -868485 479247 -885297 797358 -910090 449130 -870385 370979 -829124 -438450 -784467 -739280 -6550...
output:
497512.61565089016846741288
result:
ok found '497512.61565', expected '497512.61565', error '0.00000'
Test #8:
score: 0
Accepted
time: 10ms
memory: 4192kb
input:
3292 364845 -999918 23115 -999238 -495220 -996555 524055 -993572 419978 -990246 -441487 -988731 493394 -987187 271949 -990286 -487104 -991159 -687002 -990332 -768047 -993275 -524304 -995312 -47770 -996316 -77665 -996912 -928704 -990291 -798112 -987083 -940798 -989169 -241346 -987846 -234987 -972976 ...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
431 245611 -999674 -738083 -962850 -478189 -941103 -683461 -950693 -723371 -805609 -881791 -714279 -987279 -734606 -917431 -729365 -889819 -579494 -900362 -550372 -834907 -904231 -720665 -869101 -717255 -824019 -711973 -565569 -769652 -515548 -724811 -361500 -998030 -366800 -967623 -309405 -965964 -...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #10:
score: 0
Accepted
time: 4ms
memory: 4336kb
input:
4628 771925 -999694 -176559 -999057 559136 -997722 740255 -998118 -532115 -997228 75078 -995395 -886460 -997053 153364 -995648 107732 -995663 368365 -988307 591328 -987914 444405 -990856 376975 -989333 106701 -984376 333516 -986560 116181 -990328 -66424 -981382 191264 -987644 -210220 -991226 -68250 ...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #11:
score: 0
Accepted
time: 12ms
memory: 4184kb
input:
2937 717845 -998210 -682431 -996872 -887362 -984299 -865479 -960730 -958800 -959288 -998581 -915390 -941386 -915084 -941225 -870233 -992911 -759945 -996265 -463081 -993143 185428 -998477 309666 -999404 255022 -976930 229775 -959030 230936 -961109 234734 -972436 218732 -965431 260601 -995989 103112 -...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #12:
score: 0
Accepted
time: 19ms
memory: 4400kb
input:
4511 974292 -999476 -606738 -999096 -723712 -992306 -944394 -991809 -987714 -988923 -835882 -990546 -197898 -989906 -224486 -988631 -715774 -985857 -696734 -984655 -673361 -983650 -593114 -984945 -565742 -986117 -314889 -983507 12004 -977152 -542680 -962273 -871586 -966937 -809794 -970586 -733453 -9...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #13:
score: 0
Accepted
time: 10ms
memory: 4220kb
input:
1482 953437 -999701 -531118 -993174 -257827 -980094 -924148 -960541 -858744 -953510 -870425 -947870 -987956 -936077 -885214 -960348 -802355 -976424 -644804 -985648 -558705 -987112 -373731 -973395 -283308 -969368 -107184 -959895 -513223 -949966 -404476 -942421 -481016 -956164 -614383 -947493 -714466 ...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #14:
score: 0
Accepted
time: 11ms
memory: 5116kb
input:
10001 851814 -999848 293276 -999261 -639166 -998728 -369611 -998983 -17775 -993520 -962370 -992983 -876893 -991811 -990246 -997047 -253251 -995527 -431256 -992585 -645211 -991813 -912868 -991091 -838912 -992756 -569264 -987687 -914262 -996368 -205687 -992164 -433526 -992532 -397616 -991879 -431244 -...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #15:
score: 0
Accepted
time: 4ms
memory: 4476kb
input:
10001 336169 -999896 577082 -999822 184210 -998594 -35591 -997796 258516 -996867 34117 -996756 -391496 -997881 -727378 -998210 -682431 -998056 -958016 -990958 -970394 -986200 -957419 -974805 -973552 -959288 -998581 -960730 -958800 -956901 -936187 -949352 -941331 -944301 -942604 -951341 -963718 -9528...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #16:
score: 0
Accepted
time: 16ms
memory: 4684kb
input:
10001 788227 -999874 674874 -999099 699732 -999701 -171220 -999812 -224313 -999557 -160461 -998302 -245251 -998701 -635019 -998526 -736484 -998412 -818031 -998073 -96296 -997156 138491 -996595 -926080 -988909 -813093 -985644 -796265 -984394 -844416 -985689 -855227 -981891 -861305 -981316 -891524 -98...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #17:
score: 0
Accepted
time: 4ms
memory: 4476kb
input:
10001 198360 -999842 932608 -999523 380111 -998834 139995 -998652 -117584 -998755 850942 -998037 845586 -997580 582854 -998349 -148853 -998515 -628231 -998201 -639030 -998116 -840988 -998114 -531248 -998320 -223776 -997232 569927 -997235 168891 -995406 569364 -994666 562210 -994000 34156 -995345 -25...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #18:
score: 0
Accepted
time: 12ms
memory: 4436kb
input:
10001 327410 -999928 9352 -999585 -676208 -999113 -416060 -998934 -694011 -999013 -484553 -999191 11324 -999485 328101 -999204 546226 -998663 -864092 -999029 823882 -998181 -719693 -997646 -820651 -997029 -525350 -997576 58842 -998212 -291824 -998221 -526066 -998281 -157179 -998232 602133 -996352 -8...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
19 87 -89 23 -31 -55 72 -30 92 9 29 -32 44 33 27 17 23 20 24 1 -46 -7 41 51 80 72 -61 5 -77 22 39 94 -4 71 -22 79 -46 97 -87 61
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
13 87 -61 7 -9 -82 -5 -62 -1 -16 27 -39 22 -53 28 -81 87 10 59 -20 68 -3 9 -5 32 87 -47 -6
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
13 24 -82 74 -64 -67 -45 -13 -26 2 100 -90 71 -54 74 -21 16 -14 98 -1 92 35 84 66 97 98 14 40
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
18 23 -99 -55 -20 -81 -64 -64 69 -40 99 -97 57 -15 -11 -52 0 -22 80 11 62 100 23 96 63 73 18 14 13 77 -34 38 -24 2 -94 54 -83 -21
output:
2.95660958422126779119
result:
ok found '2.95661', expected '2.95661', error '0.00000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
16 50 -76 37 -72 -77 4 -52 19 -75 37 -44 42 -33 45 -27 64 -27 70 -65 71 -34 68 -23 78 79 8 7 -7 95 -6 39 -72 56
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
14 54 -93 -75 -29 -89 -76 -46 -38 -73 -47 -13 -13 -2 17 -65 61 -99 29 -30 85 81 84 81 -5 -7 72 90 -64 -6
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
9 44 -82 -23 17 -86 31 -12 66 -29 88 3 19 50 -33 -27 -70 -15 -55 37
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
16 73 -79 -81 -22 -93 12 -38 55 -4 94 -63 92 -10 87 98 2 92 41 40 -11 97 15 50 32 2 5 -29 -6 -63 -39 11 -42 58
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
20 62 -98 -54 -97 -60 73 -81 70 -39 1 -2 -5 12 -21 23 -31 24 -64 -29 -62 -22 -87 -8 -37 69 56 14 68 10 69 10 94 -81 76 28 28 58 -24 79 -84 41
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
9 99 -90 53 -66 -92 8 -93 -56 -37 0 -45 95 -88 -8 -30 41 49 -69 1
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #29:
score: 0
Accepted
time: 40ms
memory: 8288kb
input:
23758 42 999891 36 998928 178 999811 36 998891 178 999794 36 998852 178 999669 36 998717 178 999551 36 998128 178 999516 36 997501 178 999350 36 997181 178 999275 36 997001 178 998599 36 996786 178 998502 36 996660 178 998380 36 995557 178 998196 36 995222 178 997848 36 994381 178 997842 36 993623 1...
output:
181485.74981743216312679579
result:
ok found '181485.74982', expected '181485.74982', error '0.00000'
Test #30:
score: 0
Accepted
time: 215ms
memory: 23392kb
input:
89098 100 999972 87 999857 278 999943 87 999701 278 999659 87 999618 278 999651 87 999589 278 999621 87 999450 278 999579 87 999356 278 999553 87 999110 278 999516 87 999049 278 999443 87 998921 278 999386 87 998760 278 999353 87 998661 278 999333 87 998653 278 999307 87 998557 278 999152 87 998537 ...
output:
42.83779210370306600453
result:
ok found '42.83779', expected '42.83779', error '0.00000'
Test #31:
score: 0
Accepted
time: 44ms
memory: 6744kb
input:
17198 9 999818 3 999579 401 998839 3 999557 401 998313 3 999189 401 997890 3 998142 401 997541 3 998104 401 997100 3 998052 401 996425 3 998028 401 996340 3 997767 401 996000 3 997489 401 995998 3 996716 401 995447 3 996079 401 995059 3 995539 401 993759 3 994367 401 993753 3 993994 401 993667 3 992...
output:
19947.93107904244101291624
result:
ok found '19947.93108', expected '19947.93108', error '0.00000'
Test #32:
score: 0
Accepted
time: 20ms
memory: 6120kb
input:
12538 71 999508 -38 999900 224 999243 -38 997800 224 998518 -38 996913 224 996174 -38 996435 224 996122 -38 995267 224 995886 -38 993656 224 995158 -38 993254 224 993472 -38 991121 224 992934 -38 990973 224 992555 -38 990564 224 992374 -38 989040 224 991361 -38 988792 224 990504 -38 985959 224 98962...
output:
15527.86406502181097266657
result:
ok found '15527.86407', expected '15527.86407', error '0.00000'
Test #33:
score: 0
Accepted
time: 168ms
memory: 24188kb
input:
65730 79 999935 18 999936 311 999932 18 999770 311 999898 18 999749 311 999772 18 999643 311 999668 18 999362 311 999490 18 999332 311 998865 18 999310 311 998792 18 998986 311 998676 18 998971 311 998569 18 998863 311 998384 18 998748 311 998198 18 998650 311 997974 18 998631 311 997502 18 998581 3...
output:
741.21037208723095091045
result:
ok found '741.21037', expected '741.21037', error '0.00000'
Test #34:
score: 0
Accepted
time: 124ms
memory: 14336kb
input:
52762 24 999966 -12 999655 270 999878 -12 999605 270 999663 -12 999574 270 999643 -12 999485 270 999503 -12 999466 270 999442 -12 999434 270 999266 -12 999366 270 999237 -12 999295 270 999170 -12 999187 270 999110 -12 999165 270 998894 -12 999133 270 998819 -12 998892 270 998544 -12 998867 270 99844...
output:
51298.20692316766223939339
result:
ok found '51298.20692', expected '51298.20692', error '0.00000'
Test #35:
score: 0
Accepted
time: 51ms
memory: 8180kb
input:
22030 10 999623 -4 999638 312 999583 -4 999535 312 999533 -4 998106 312 998365 -4 997779 312 997727 -4 997682 312 997552 -4 997449 312 997546 -4 997246 312 996821 -4 994236 312 996487 -4 993684 312 996172 -4 992726 312 995518 -4 992509 312 995195 -4 992346 312 995160 -4 991850 312 994853 -4 991802 3...
output:
761340.77232749816039358848
result:
ok found '761340.77233', expected '761340.77233', error '0.00000'
Test #36:
score: 0
Accepted
time: 108ms
memory: 15924kb
input:
87406 33 999996 33 999948 110 999992 33 999782 110 999920 33 999667 110 999919 33 999343 110 999668 33 999327 110 999613 33 999312 110 999607 33 999288 110 999375 33 999229 110 999213 33 999091 110 999033 33 999076 110 998809 33 999054 110 998753 33 999049 110 998698 33 999014 110 998558 33 998846 1...
output:
28667.82110435164003092723
result:
ok found '28667.82110', expected '28667.82110', error '0.00000'
Test #37:
score: 0
Accepted
time: 65ms
memory: 7340kb
input:
27382 91 999756 88 999773 105 998972 88 999759 105 998867 88 999730 105 998638 88 999367 105 998591 88 999329 105 998512 88 999318 105 998398 88 998870 105 998334 88 998818 105 997611 88 998434 105 997005 88 998338 105 996684 88 998073 105 996666 88 997242 105 996538 88 997154 105 996383 88 996911 1...
output:
2698.56136562425416514088
result:
ok found '2698.56137', expected '2698.56137', error '0.00000'
Test #38:
score: 0
Accepted
time: 168ms
memory: 17652kb
input:
78350 61 999971 21 999982 211 999858 21 999969 211 999751 21 999876 211 999742 21 999632 211 999648 21 999606 211 999613 21 999600 211 999578 21 999596 211 999462 21 999577 211 999384 21 999405 211 999335 21 999356 211 998897 21 999258 211 998879 21 999209 211 998651 21 999152 211 998395 21 999151 2...
output:
2180.24768106521725030689
result:
ok found '2180.24768', expected '2180.24768', error '0.00000'
Test #39:
score: 0
Accepted
time: 19ms
memory: 5568kb
input:
19372 42 1000000 779761 998891 779761 998891 13 998852 13 998852 779761 998717 779761 998717 -14 998128 -14 998128 779761 997501 779761 997501 -2 997181 -2 997181 779761 997001 779761 997001 -2 996786 -2 996786 779761 996660 779761 996660 39 995557 39 995557 779761 995222 779761 995222 -10 993623 -1...
output:
398726.54293524845587626260
result:
ok found '398726.54294', expected '398726.54294', error '0.00000'
Test #40:
score: 0
Accepted
time: 79ms
memory: 15064kb
input:
78564 8 1000000 829540 999637 829540 999637 7 999618 7 999618 829540 999589 829540 999589 8 999426 8 999426 829540 999049 829540 999049 8 999004 8 999004 829540 998760 829540 998760 8 998661 8 998661 829540 998653 829540 998653 7 998557 7 998557 829540 998480 829540 998480 7 998319 7 998319 829540 9...
output:
697371.36384440444663823655
result:
ok found '697371.36384', expected '697371.36384', error '0.00000'
Test #41:
score: 0
Accepted
time: 34ms
memory: 5516kb
input:
18340 57 1000000 346830 999023 346830 999023 14 999007 14 999007 346830 998820 346830 998820 3 998313 3 998313 346830 997489 346830 997489 12 997360 12 997360 346830 995764 346830 995764 21 995562 21 995562 346830 995260 346830 995260 28 994866 28 994866 346830 994608 346830 994608 56 993822 56 9938...
output:
332728.33254798711840294345
result:
ok found '332728.33255', expected '332728.33255', error '0.00000'
Test #42:
score: 0
Accepted
time: 137ms
memory: 18848kb
input:
87372 39 1000000 200793 999952 200793 999952 14 999906 14 999906 200793 999884 200793 999884 -12 999883 -12 999883 200793 999859 200793 999859 17 999848 17 999848 200793 999809 200793 999809 -24 999795 -24 999795 200793 999762 200793 999762 18 999759 18 999759 200793 999699 200793 999699 36 999698 3...
output:
182507.86678184206050445937
result:
ok found '182507.86678', expected '182507.86678', error '0.00000'
Test #43:
score: 0
Accepted
time: 31ms
memory: 8556kb
input:
46716 57 1000000 705268 999898 705268 999898 -40 999772 -40 999772 705268 999362 705268 999362 27 998971 27 998971 705268 998792 705268 998792 25 998650 25 998650 705268 998631 705268 998631 16 998384 16 998384 705268 998379 705268 998379 -53 997769 -53 997769 705268 997502 705268 997502 1 997492 1 ...
output:
568090.25105150558221112078
result:
ok found '568090.25105', expected '568090.25105', error '0.00000'
Test #44:
score: 0
Accepted
time: 43ms
memory: 6816kb
input:
23652 69 1000000 871420 998038 871420 998038 36 996765 36 996765 871420 996651 871420 996651 39 996546 39 996546 871420 995740 871420 995740 61 995479 61 995479 871420 995360 871420 995360 32 995239 32 995239 871420 995227 871420 995227 26 995222 26 995222 871420 994586 871420 994586 24 994354 24 99...
output:
284513.72456766538306283110
result:
ok found '284513.72457', expected '284513.72457', error '0.00000'
Test #45:
score: 0
Accepted
time: 96ms
memory: 14136kb
input:
73788 70 1000000 684240 999655 684240 999655 40 999605 40 999605 684240 999574 684240 999574 54 999503 54 999503 684240 999485 684240 999485 46 999466 46 999466 684240 999453 684240 999453 50 999434 50 999434 684240 999366 684240 999366 52 999295 52 999295 684240 999237 684240 999237 58 999187 58 99...
output:
87818.28438976828840623057
result:
ok found '87818.28439', expected '87818.28439', error '0.00000'
Test #46:
score: 0
Accepted
time: 64ms
memory: 12000kb
input:
43980 79 1000000 513263 999623 513263 999623 1 999583 1 999583 513263 999535 513263 999535 63 999533 63 999533 513263 998365 513263 998365 68 998106 68 998106 513263 997779 513263 997779 -26 997727 -26 997727 513263 997682 513263 997682 15 997552 15 997552 513263 997546 513263 997546 -6 997449 -6 99...
output:
152516.43671464991922448462
result:
ok found '152516.43671', expected '152516.43671', error '0.00000'
Test #47:
score: 0
Accepted
time: 63ms
memory: 8628kb
input:
38372 61 1000000 974881 999667 974881 999667 58 999343 58 999343 974881 999312 974881 999312 8 999288 8 999288 974881 999091 974881 999091 -29 999076 -29 999076 974881 999054 974881 999054 46 999014 46 999014 974881 998255 974881 998255 17 998132 17 998132 974881 998066 974881 998066 48 997973 48 99...
output:
252559.06562060308658601571
result:
ok found '252559.06562', expected '252559.06562', error '0.00000'
Test #48:
score: 0
Accepted
time: 92ms
memory: 14288kb
input:
61596 26 1000000 605003 999688 605003 999688 18 999607 18 999607 605003 999596 605003 999596 -2 999588 -2 999588 605003 999375 605003 999375 -1 999214 -1 999214 605003 998858 605003 998858 14 998809 14 998809 605003 998590 605003 998590 -4 998557 -4 998557 605003 998172 605003 998172 -4 998054 -4 99...
output:
326248.47641289893101657071
result:
ok found '326248.47641', expected '326248.47641', error '0.00000'
Test #49:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
706 553084 -1000000 146399 -999926 140164 -999983 133722 -999908 110930 -999934 105260 -999999 105200 -999952 95962 -999942 72469 -999950 72089 -999938 54367 -999925 51331 -999906 36316 -999928 31760 -999993 30263 -999904 20816 -999948 7597 -999910 6526 -999949 6092 -999952 -6864 -999977 -39129 -999...
output:
104987.59628285497714728081
result:
ok found '104987.59628', expected '104987.59628', error '0.00000'
Test #50:
score: 0
Accepted
time: 3ms
memory: 4068kb
input:
448 929649 -999999 -915718 -995302 -929610 -975675 -929690 -933078 -929672 -926181 -929675 -923555 -929670 -914897 -929659 -893093 -929659 -842850 -929626 -806908 -929669 -800237 -929699 -791320 -929685 -781307 -929629 -724467 -929632 -716252 -929625 -711614 -929619 -666412 -929615 -665911 -929642 -...
output:
23435.61269996911754631697
result:
ok found '23435.61270', expected '23435.61270', error '0.00000'
Test #51:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
622 75451 -1000000 29393 -999999 19749 -999989 17732 -999941 11259 -999952 4756 -999907 4480 -999994 2786 -999922 -402 -999945 -4754 -999962 -5627 -999984 -10400 -999905 -10463 -999994 -16724 -999967 -20371 -999924 -24608 -999916 -41902 -999963 -42219 -999957 -69285 -999978 -72408 -999934 -74569 -99...
output:
376537.46499486429246417174
result:
ok found '376537.46499', expected '376537.46499', error '0.00000'
Test #52:
score: 0
Accepted
time: 0ms
memory: 4140kb
input:
899 754715 -1000000 17037 -999904 2543 -999994 -2423 -999958 -6464 -999917 -9416 -999969 -11970 -999992 -30146 -999966 -40560 -999998 -46965 -999998 -53911 -999917 -54853 -999949 -63825 -999963 -69333 -999935 -69672 -999903 -73875 -999936 -85717 -999919 -94916 -999996 -111536 -999912 -127465 -999964...
output:
46173.38149765563312598715
result:
ok found '46173.38150', expected '46173.38150', error '0.00000'
Test #53:
score: 0
Accepted
time: 5ms
memory: 4052kb
input:
870 139405 -1000000 103686 -999911 99940 -999946 88715 -999994 85911 -999957 84523 -999980 81935 -999932 81408 -999992 78898 -999916 61842 -999950 61662 -999979 56264 -999937 46054 -999957 45491 -999957 31319 -999903 23401 -999929 22229 -999978 21867 -999907 20397 -999926 9634 -999904 8281 -999918 2...
output:
250201.42612778861217748272
result:
ok found '250201.42613', expected '250201.42613', error '0.00000'
Test #54:
score: 0
Accepted
time: 16ms
memory: 5188kb
input:
10001 533288 -1000000 -505112 -999983 -507116 -999921 -507383 -999955 -508208 -999942 -509194 -999930 -509213 -999945 -509392 -999962 -509955 -999958 -510356 -999981 -512164 -999938 -513418 -999937 -514001 -999913 -514801 -999996 -515569 -999965 -515744 -999932 -515858 -999985 -517458 -999988 -51799...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #55:
score: 0
Accepted
time: 23ms
memory: 4712kb
input:
10001 32863 -1000000 9497 -999946 9448 -999974 9088 -999967 9080 -999979 8976 -999914 8935 -999973 8349 -999987 8292 -999951 7891 -999929 7845 -999956 7578 -999916 7327 -999981 7184 -999923 7095 -999972 7080 -999942 6775 -999969 6574 -999999 6351 -999961 6324 -999954 5265 -999944 5014 -999934 4810 -...
output:
5048.77994990591014357051
result:
ok found '5048.77995', expected '5048.77995', error '0.00000'
Test #56:
score: 0
Accepted
time: 12ms
memory: 5092kb
input:
10001 670187 -1000000 -602542 -999990 -602944 -999949 -603301 -999992 -606053 -999902 -606102 -999931 -606890 -999923 -607185 -999956 -608707 -999905 -608825 -999940 -608995 -999966 -612452 -999970 -613204 -999953 -613351 -999918 -613752 -999925 -614886 -999905 -615022 -999939 -615165 -999933 -61578...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #57:
score: 0
Accepted
time: 16ms
memory: 5176kb
input:
10001 615401 -1000000 -558432 -999938 -558469 -999982 -558771 -999942 -559219 -999955 -559675 -999958 -560278 -999989 -560419 -999921 -561084 -999990 -561231 -999985 -561766 -999957 -562064 -999991 -562374 -999974 -563955 -999974 -564375 -999983 -564847 -999989 -565146 -999908 -566758 -999992 -56766...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #58:
score: 0
Accepted
time: 20ms
memory: 4844kb
input:
10000 243265 -1000000 -206787 -999936 -207691 -999965 -207721 -999906 -208147 -999959 -208203 -999906 -208403 -999988 -208691 -999961 -209114 -999952 -209609 -999940 -211921 -999934 -212408 -999952 -212713 -999957 -213352 -999966 -213875 -999999 -214448 -999942 -214523 -999997 -215035 -999965 -21528...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #59:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 9277 -9912 -6898 -9471 -9279 5751 -9301 -3912 9306
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #60:
score: 0
Accepted
time: 1ms
memory: 4068kb
input:
60 1041 -9987 9 -9914 -1019 -9858 -1078 -8990 -1042 -8768 -1030 -7902 -1012 -7349 -1017 -7247 -1035 -7098 -1016 -7051 -1007 -5132 -1090 -3995 -1063 -3212 -1079 -2038 -1064 -2030 -1005 -1750 -1004 -1636 -1085 -1278 -1041 -989 -1056 -880 -1013 1274 -1035 2292 -1079 3196 -1018 4668 -998 4934 -1038 5692...
output:
2644.52100980879854819072
result:
ok found '2644.52101', expected '2644.52101', error '0.00000'
Test #61:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
67 9843 -9998 -3569 -9905 -5210 -9918 -6674 -9949 -8695 -9652 -9847 -9539 -9851 -9502 -9844 -8940 -9818 -7516 -9838 -5941 -9807 -5831 -9836 -4871 -9873 -4692 -9877 -3079 -9855 -527 -9854 132 -9828 209 -9803 3557 -9882 8307 -9852 8458 -9857 9152 -9853 9947 -9769 9975 -7455 9975 45 9997 688 9951 2908 ...
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #62:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
15 4953 -10000 3489 -9935 2828 -9934 1018 -9943 -4226 -4172 -4994 2551 -4912 4798 -5002 7023 -4947 9989 -4078 9951 -3074 9908 934 9225 4966 7174 4991 6983 4947 -7661 4988
output:
4470.51456522747734201317
result:
ok found '4470.51457', expected '4470.51457', error '0.00000'
Test #63:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
44 5240 -9985 4881 -9919 4550 -9969 3986 -9956 3883 -9973 53 -9928 -1313 -9951 -2552 -9976 -3631 -8436 -5245 -5392 -5249 -1633 -5206 -1352 -5239 -592 -5252 897 -5210 1006 -5269 2138 -5196 3873 -5282 4600 -5261 7205 -5211 7560 -5259 8263 -5213 9021 -5234 9920 -5112 9973 -4131 9985 -941 9980 -783 9960...
output:
1577.92985802175675846826
result:
ok found '1577.92986', expected '1577.92986', error '0.00000'
Test #64:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
4 1 1000000 1000000 -999999 -999994 -1000000 1000000 -999999 -1000000
output:
0.17157896105630966174
result:
ok found '0.17158', expected '0.17158', error '0.00000'
Test #65:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
4 1 1000000 1 999998 1 999997 -1000000 1000000 -1000000
output:
0.00000099999851954635
result:
ok found '0.00000', expected '0.00000', error '0.00000'
Test #66:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
4 1 99948 1 99947 -99950 99950 -99950 99950 1
output:
0.00001000485235636006
result:
ok found '0.00001', expected '0.00001', error '0.00000'
Test #67:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 499999 -499998 1000000 500000 1000000 499999 -1000000 -499999 -999950
output:
0.00001237530958523537
result:
ok found '0.00001', expected '0.00001', error '0.00000'
Test #68:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
4 499999 -499999 -1000000 499999 -999950 499998 1000000 -500000 1000000
output:
0.00001237530958523537
result:
ok found '0.00001', expected '0.00001', error '0.00000'
Test #69:
score: 0
Accepted
time: 216ms
memory: 23900kb
input:
100000 50000 -997263 -48631 -997262 1371 -997261 -48630 -997260 1372 -997259 -48629 -997258 1373 -997257 -48628 -997256 1374 -997255 -48627 -997254 1375 -997253 -48626 -997252 1376 -997251 -48625 -997250 1377 -997249 -48624 -997248 1378 -997247 -48623 -997246 1379 -997245 -48622 -997244 1380 -997243...
output:
0.99995000239982800849
result:
ok found '0.99995', expected '0.99995', error '0.00000'
Test #70:
score: 0
Accepted
time: 143ms
memory: 20228kb
input:
100000 1 -949960 -949959 -949958 949960 949960 949959 949959 -949958 -949948 -949948 -949949 949950 949948 949950 949950 -949948 -949938 -949939 -949940 949940 949939 949939 949940 -949938 -949929 -949928 -949928 949928 949930 949930 949928 -949928 -949920 -949919 -949920 949918 949919 949919 949920...
output:
25713.00034332207877696419
result:
ok found '25713.00034', expected '25713.00035', error '0.00000'
Test #71:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
4 10 2 -14 14 2 -2 14 -14 -2
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #72:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
4 30 -100 0 0 -100 100 0 0 100
output:
115.14718625761429707938
result:
ok found '115.14719', expected '115.14719', error '0.00000'
Test #73:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
8 723777 885124 -723777 885124 -514064 514064 885124 514064 723777 -514064 723777 -514064 885124 -885124 -514064 -885124 -723777
output:
0.00001000580338725198
result:
ok found '0.00001', expected '0.00001', error '0.00000'
Test #74:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
4 499999 -1000000 -500000 1000000 -499999 1000000 500000 -1000000 499998
output:
500000.75000051619997520902
result:
ok found '500000.75000', expected '500000.75000', error '0.00000'
Test #75:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
3 10000 300000 300000 600000 600000 400000 500000
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #76:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
3 100000 300000 300000 600000 600000 400000 500000
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #77:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
28 100 0 -100 300 -100 300 200 1200 200 1200 -100 1500 -100 1500 200 2400 200 2400 -100 2700 -100 2700 200 3600 200 3600 -200 3300 -200 3300 100 3000 100 3000 -200 2100 -200 2100 100 1800 100 1800 -200 900 -200 900 100 600 100 600 -500 3900 -500 3900 500 0 500
output:
700.00000000000000000000
result:
ok found '700.00000', expected '700.00000', error '0.00000'
Test #78:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
28 100 0 -100 200 -100 200 200 1200 200 1200 -100 1400 -100 1400 200 2400 200 2400 -100 2600 -100 2600 200 3600 200 3600 -200 3300 -200 3300 100 3100 100 3100 -200 2100 -200 2100 100 1900 100 1900 -200 900 -200 900 100 700 100 700 -500 3800 -500 3800 500 0 500
output:
0.00000000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #79:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
9 1 10 5 5 5 5 -5 -5 -5 -4 0 -5 5 -10 5 -10 -10 10 -10
output:
6.98019609728144303350
result:
ok found '6.98020', expected '6.98020', error '0.00000'
Test #80:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
9 1 10 5 5 5 6 0 5 -5 -5 -5 -5 5 -10 5 -10 -10 10 -10
output:
5.00000000000000000000
result:
ok found '5.00000', expected '5.00000', error '0.00000'
Test #81:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
16 100 -1000 -1000 -1 -1000 -1 -1 -100 0 100 0 1 -1 1 -1000 1000 -1000 1000 -1 900 0 1000 1 1000 1000 -1000 1000 -1000 1 -900 0 -1000 -1
output:
1200.00000000000000000000
result:
ok found '1200.00000', expected '1200.00000', error '0.00000'
Test #82:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
125 1 -1074 -727 -1000 -788 -944 -804 -863 -802 -807 -770 -727 -696 -677 -696 -627 -726 -542 -793 -474 -812 -413 -811 -333 -774 -230 -704 -205 -695 -155 -695 -43 -737 38 -753 136 -750 205 -699 258 -663 258 -616 106 -616 -37 -560 -232 -421 23 -399 374 -341 625 -252 639 -333 626 -431 480 -570 259 -616...
output:
406.42600651669077352346
result:
ok found '406.42601', expected '406.42601', error '0.00000'