QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519499 | #1463. Closest Pair Algorithm | crimson231 | AC ✓ | 5065ms | 397928kb | C++17 | 10.0kb | 2024-08-14 20:33:10 | 2024-08-14 20:33:10 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <cassert>
#include <cstdint>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ll INF = 1e18;
const int LEN = 250;
const ld TOL = 1e-9;
const ld PI = acos(-1);
inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL ? 1 : 0; }
inline bool zero(const ld& x) { return !sign(x); }
inline void norm(ld x) {
while (sign(x) < 0) x += 2 * PI;
while (sign(x - 2 * PI) >= 0) x -= 2 * PI;
return;
}
int N, M, E, OD[LEN], Q[LEN];
ld ANS[LEN][LEN];
struct Pos {
int x, y;
Pos(int X = 0, int Y = 0) : x(X), y(Y) {}
bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
bool operator != (const Pos& p) const { return x != p.x || y != p.y; }
bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
bool operator <= (const Pos& p) const { return x == p.x ? y <= p.y : x <= p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
Pos operator * (const int& n) const { return { x * n, y * n }; }
Pos operator / (const int& n) const { return { x / n, y / n }; }
ll operator * (const Pos& p) const { return (ll)x * p.x + (ll)y * p.y; }
ll operator / (const Pos& p) const { return (ll)x * p.y - (ll)y * p.x; }
Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
Pos& operator *= (const int& scale) { x *= scale; y *= scale; return *this; }
Pos& operator /= (const int& scale) { x /= scale; y /= scale; return *this; }
Pos operator - () const { return { -x, -y }; }
Pos operator ~ () const { return { -y, x }; }
Pos operator ! () const { return { y, x }; }
ll xy() const { return (ll)x * y; }
ll Euc() const { return (ll)x * x + y * y; }
int Man() const { return std::abs(x) + std::abs(y); }
ld mag() const { return hypot(x, y); }
ld rad() const { return atan2(y, x); }
friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
int quad() const { return y > 0 || y == 0 && x >= 0; }
friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
} P[LEN];
const Pos O = { 0, 0 }, INVAL = { -1, -1 };
typedef std::vector<Pos> Polygon;
ll cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
ll cross(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) / (d4 - d3); }
ll dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
ll dot(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { ll ret = cross(d1, d2, d3, d4); return ret < 0 ? -1 : !!ret; }
ld projection(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d1) / (d2 - d1).mag(); }
ld projection(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3) / (d2 - d1).mag(); }
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && dot(d1, d3, d2) >= 0; }
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && dot(d1, d3, d2) > 0; }
bool collinear(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return !ccw(d1, d2, d3) && !ccw(d1, d2, d4); }
bool intersect(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2, const bool f = 1) {
//f : include end of seg, !f : ignore end of seg
bool f1 = ccw(s1, s2, d1) * ccw(s2, s1, d2) > 0;
bool f2 = ccw(d1, d2, s1) * ccw(d2, d1, s2) > 0;
if (!f) return f1 && f2;
bool f3 = on_seg_strong(s1, s2, d1) ||
on_seg_strong(s1, s2, d2) ||
on_seg_strong(d1, d2, s1) ||
on_seg_strong(d1, d2, s2);
return (f1 && f2) || f3;
}
struct Seg {
short int u, v;//idx
Seg(short int u = 0, short int v = 0) : u(u), v(v) {}
Pos s() const { return P[v] - P[u]; }
Pos p() const { return Pos(u, v); }
int ccw(const Pos& p0) const { return sign(cross(P[u], P[v], p0)); }
bool operator < (const Seg& S) const {
assert(O != s()); assert(O != S.s());
bool f1 = O < s();
bool f2 = O < S.s();
if (f1 != f2) return f1;
ll CCW = s() / S.s();
return !CCW ? S.ccw(P[u]) > 0 : CCW < 0;
//return !CCW ? !S.ccw(P[u]) ? p() < S.p() : S.ccw(P[u]) > 0 : CCW < 0;
}
bool operator == (const Seg& S) const { return s() / S.s() == 0 && s() * S.s() > 0; }
} events[LEN * LEN];
struct Slope {
Seg seg;
ld ans;
Slope(Seg se = Seg(0, 0), ld a = 0) : seg(se), ans(a) {}
};
typedef std::vector<Slope> vslope;
typedef std::vector<Seg> vseg;
typedef std::vector<ld> vld;
vslope slopes[LEN][LEN];
vseg segs[LEN][LEN];
vld angs[LEN][LEN];
ld dist(const Pos& p, const Pos& q) { return (p - q).mag(); }
ld sweep(const int& i, const int& j) {
Pos I, J;
I = P[i], J = P[j];
auto theta = [&](const Pos& vec) -> ld {
Pos K = -~(J - I);
return rad(K, vec);
};
ld total = 0;
const vseg& SS = segs[i][j];
const vld& AA = angs[i][j];
const int sz = SS.size();
for (int k = 0; k < sz; k++) {
const Seg& S0 = SS[k], & S1 = SS[(k + 1) % sz];
const ld& A0 = AA[k], & A1 = AA[(k + 1) % sz];
if (sign(A0) <= 0) continue;
ld len = (J - I).mag();
ld hi = std::min(theta(S0.s()), (ld)(PI * .5));
ld lo = std::max(theta(S1.s()), -(ld)(PI * .5));
if (sign(A0 - len) >= 0) {
total += hi - lo;
continue;
}
ld ratio = std::max(-(ld)1., std::min((ld)1., (ld)(A0 / len)));
ld phi = acos(ratio);
if (sign(hi - phi) > 0) {
if (sign(lo - phi) > 0) total += hi - lo;
else total += hi - phi;
}
if (sign(lo + phi) < 0) {
if (sign(hi + phi) < 0) total += -(lo - hi);
else total += -(lo + phi);
}
}
return total;
}
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(10);
memset(P, 0, sizeof P);
memset(Q, 0, sizeof Q);
memset(OD, 0, sizeof OD);
std::cin >> N;
if (N == 2) { std::cout << "1.0000000000\n"; return; }
for (int i = 0; i < N; i++) std::cin >> P[i];
std::sort(P, P + N);
for (int i = 0; i < N; i++) OD[i] = i, Q[i] = i;
E = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
events[E++] = Seg(i, j);
events[E++] = Seg(j, i);
}
}
std::sort(events, events + E);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
ANS[i][j] = -INF;
ld ans = INF;
for (int i = 0; i < N; i++) {
for (int j = i - 1; j >= 0; j--) {
ANS[i][j] = ans;
ans = std::min(ans, dist(P[i], P[j]));
}
}
for (int i = 0; i < E; i++) {
int u = events[i].u, v = events[i].v;
int ou = OD[u], ov = OD[v];
OD[u] = ov; OD[v] = ou;
Q[ou] = v; Q[ov] = u;
assert(ov - ou == 1);
ans = ou <= 1 ? INF : ANS[Q[ou - 1]][Q[0]];
if (ou >= 2) ans = std::min(ans, dist(P[Q[0]], P[Q[ou - 1]]));
for (int j = ou - 1; j >= 0; j--) {
ANS[v][Q[j]] = ans;
//slopes[v][Q[j]].push_back(Slope(Seg(u, v), ans));
segs[v][Q[j]].push_back(Seg(u, v));
angs[v][Q[j]].push_back(ans);
ans = std::min(ans, dist(P[v], P[Q[j]]));
}
for (int j = ov - 1; j >= 0; j--) {
ANS[u][Q[j]] = ans;
//slopes[u][Q[j]].push_back(Slope(Seg(u, v), ans));
segs[u][Q[j]].push_back(Seg(u, v));
angs[u][Q[j]].push_back(ans);
ans = std::min(ans, dist(P[u], P[Q[j]]));
}
if (ov < N - 1) {
ANS[Q[ov + 1]][u] = ans;
//slopes[Q[ov + 1]][u].push_back(Slope(Seg(u, v), ans));
segs[Q[ov + 1]][u].push_back(Seg(u, v));
angs[Q[ov + 1]][u].push_back(ans);
ans = std::min(ans, dist(P[u], P[Q[ov + 1]]));
ANS[Q[ov + 1]][v] = ans;
//slopes[Q[ov + 1]][v].push_back(Slope(Seg(u, v), ans));
segs[Q[ov + 1]][v].push_back(Seg(u, v));
angs[Q[ov + 1]][v].push_back(ans);
ans = std::min(ans, dist(P[v], P[Q[ov + 1]]));
ans = std::min(ans, ANS[Q[ov + 1]][Q[0]]);
}
for (int j = ov + 2; j < N; j++) {
ans = std::min(ans, ANS[Q[j]][Q[0]]);
ANS[Q[j]][u] = ans;
//slopes[Q[j]][u].push_back(Slope(Seg(u, v), ans));
segs[Q[j]][u].push_back(Seg(u, v));
angs[Q[j]][u].push_back(ans);
ans = std::min(ans, dist(P[u], P[Q[j]]));
ANS[Q[j]][v] = ans;
//slopes[Q[j]][v].push_back(Slope(Seg(u, v), ans));
segs[Q[j]][v].push_back(Seg(u, v));
angs[Q[j]][v].push_back(ans);
ans = std::min(ans, dist(P[v], P[Q[j]]));
}
//slopes[v][u].push_back(Slope(Seg(u, v), -INF));
segs[v][u].push_back(Seg(u, v));
angs[v][u].push_back(-INF);
}
ld total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) continue;
total += sweep(i, j);
}
}
std::cout << total / (2 * PI) << "\n";
//std::cout << "Size of Pos: " << sizeof(Pos) << " bytes\n";
//std::cout << "Size of Seg: " << sizeof(Seg) << " bytes\n";
//std::cout << "Size of Slope: " << sizeof(Slope) << " bytes\n";
return;
}
int main() { solve(); return 0; }//boj18497
//Petrozavodsk Programming Camp > Winter 2020 > Day 8: Almost Algoritmic Contest J
/*
3
-1000000 0
1000000 0
1000000 1
1.5000004
5
4 -10
-3 0
-8 6
-9 4
-5 0
3.4242720071
5
-395 310
597 -448
-290 300
-352 -283
-499 -368
2.8473923420
30
-938 702
950 -131
-649 190
431 793
29 606
-887 -555
742 265
-972 419
-28 -399
-316 727
-654 160
-74 694
168 438
-997 604
-430 -836
809 -790
-581 516
677 -721
947 976
-559 -140
-692 -902
-828 927
-562 711
258 -715
761 243
143 -106
803 -109
-760 430
-264 -146
270 905
21.4411311891
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8888kb
input:
4 0 0 0 1 1 0 1 1
output:
5.0000000000
result:
ok found '5.0000000', expected '5.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8816kb
input:
3 0 0 0 1 1 0
output:
2.5000000000
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8332kb
input:
2 3 4 5 6
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 8840kb
input:
3 -1000000 0 1000000 0 1000000 1
output:
1.5000003979
result:
ok found '1.5000004', expected '1.5000004', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 8884kb
input:
5 4 -10 -3 0 -8 6 -9 4 -5 0
output:
3.4242720071
result:
ok found '3.4242720', expected '3.4242720', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 8888kb
input:
5 -395 310 597 -448 -290 300 -352 -283 -499 -368
output:
2.8473923420
result:
ok found '2.8473923', expected '2.8473923', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8664kb
input:
10 -6 -1 10 -6 -7 -8 2 -5 -9 -5 -2 1 3 -2 9 -10 -1 5 1 -1
output:
11.5335911149
result:
ok found '11.5335911', expected '11.5335911', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 8896kb
input:
10 -563 -366 -256 502 904 625 773 -242 470 920 -873 -152 369 339 109 110 714 762 107 -69
output:
9.7395960245
result:
ok found '9.7395960', expected '9.7395960', error '0.0000000'
Test #9:
score: 0
Accepted
time: 6ms
memory: 9664kb
input:
30 4 10 10 -6 -7 -9 3 2 5 -3 -2 -1 9 -10 2 -7 6 9 -5 5 5 10 -3 -4 -3 0 -2 9 0 7 2 8 10 -4 3 5 4 -6 7 -1 -8 2 -8 -3 6 4 -9 0 -1 -8 -7 1 7 4 -1 -7 9 -9 1 -8
output:
39.8173317024
result:
ok found '39.8173317', expected '39.8173317', error '0.0000000'
Test #10:
score: 0
Accepted
time: 10ms
memory: 9744kb
input:
30 -938 702 950 -131 -649 190 431 793 29 606 -887 -555 742 265 -972 419 -28 -399 -316 727 -654 160 -74 694 168 438 -997 604 -430 -836 809 -790 -581 516 677 -721 947 976 -559 -140 -692 -902 -828 927 -562 711 258 -715 761 243 143 -106 803 -109 -760 430 -264 -146 270 905
output:
21.4411311891
result:
ok found '21.4411312', expected '21.4411312', error '0.0000000'
Test #11:
score: 0
Accepted
time: 64ms
memory: 14576kb
input:
60 -57 70 -55 -35 -76 21 -30 56 -19 75 66 96 3 -57 -94 4 64 30 48 -38 43 6 92 15 -47 -78 -85 -24 84 -18 -27 28 -81 70 93 8 -79 -100 -45 55 85 20 -79 -98 -46 -86 -65 45 -35 -39 -92 -29 38 -11 97 59 -29 22 -18 72 -73 26 -81 -49 -99 3 89 72 -3 -99 -13 17 -60 -81 21 -71 -14 34 -31 -73 -16 -75 -48 42 54 ...
output:
50.7164955703
result:
ok found '50.7164956', expected '50.7164956', error '0.0000000'
Test #12:
score: 0
Accepted
time: 59ms
memory: 14712kb
input:
60 -1770 -5520 -5544 3148 -1744 4969 7804 -9016 6952 9818 447 -8049 -6123 -6377 7183 -6928 -9778 2246 2132 3608 -9801 3893 3 4803 9027 -6153 -8625 725 5761 9073 -2283 -4292 -6925 -2400 9303 8826 -3585 -6206 -346 5393 8416 -6776 -9629 -4611 1656 8044 -7135 -9368 2235 -1434 9832 -5980 4977 -6167 887 -...
output:
62.8398163588
result:
ok found '62.8398164', expected '62.8398164', error '0.0000000'
Test #13:
score: 0
Accepted
time: 51ms
memory: 14788kb
input:
60 -163498 -30302 -345724 646083 -612360 -740665 678763 305271 -773339 301150 -519423 553953 -87625 -832281 -164733 476742 62019 199517 916534 -968558 -504532 787190 830366 -364158 -432172 840849 -702154 722780 -881679 -826972 969462 -387613 34095 -130739 736702 -916629 465648 485860 -596725 797379 ...
output:
64.1098302827
result:
ok found '64.1098303', expected '64.1098303', error '0.0000000'
Test #14:
score: 0
Accepted
time: 291ms
memory: 40276kb
input:
100 55 100 45 95 -71 33 70 -100 -17 85 -76 78 -83 -1 -87 67 -31 -76 17 96 -18 66 -80 -41 -58 -10 56 72 4 19 -56 75 -77 -79 33 -86 9 -30 54 5 -31 94 84 50 -45 75 45 -69 70 -5 -40 12 98 31 99 -31 46 -49 -98 -85 73 51 61 -10 -82 25 -37 -78 -1 44 2 -75 98 -61 61 -29 -83 -7 53 -19 -58 33 88 -9 88 6 95 50...
output:
102.5036853191
result:
ok found '102.5036853', expected '102.5036853', error '0.0000000'
Test #15:
score: 0
Accepted
time: 285ms
memory: 40340kb
input:
100 -2145 -3976 6481 1795 2773 6858 968 1068 3020 410 6842 5269 -4046 5388 -8540 -7364 -8675 -8325 7475 -7112 -5952 -8190 -8780 52 5610 -6970 6140 3806 -3880 -1842 -6763 -5660 1347 6636 4900 4245 -7529 4879 391 4629 3006 -1823 -8983 8300 -7285 -643 -9430 7059 -737 -8747 1865 -7802 -1523 7841 6239 -1...
output:
93.3476354560
result:
ok found '93.3476355', expected '93.3476355', error '0.0000000'
Test #16:
score: 0
Accepted
time: 284ms
memory: 40688kb
input:
100 -921745 691002 -962015 -160749 -480023 -34066 -343131 -110768 -231448 -403357 106013 34960 896030 -598173 -127337 544913 -381132 505651 138159 311881 -646788 31263 -120639 242108 -565258 738932 865191 -116949 295077 -87673 -73628 -517530 850182 -677471 994023 -826688 -567069 436849 921215 336313...
output:
102.0997096650
result:
ok found '102.0997097', expected '102.0997097', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2465ms
memory: 258532kb
input:
200 -9443 -8106 4368 4606 8058 7890 453 -776 -7768 -289 -1757 -8854 -8404 3535 -2576 -4678 -6462 -7679 -8980 -9693 -1243 -8214 4956 6575 -3882 -7199 -1326 -7967 -5234 3605 -4341 -382 -3869 4314 -4835 -550 2136 -3197 2496 -2888 -9330 2380 3664 -7934 -9549 -3014 2763 -7755 6846 -9655 -8124 -2063 -2566...
output:
338.6896033383
result:
ok found '338.6896033', expected '338.6896033', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2432ms
memory: 258132kb
input:
200 525065 434645 -624702 -527174 -717713 -766539 -473771 -936088 14914 -141548 -751249 239135 1827 191797 -419595 678678 412154 899832 -575551 541949 -621213 643205 -466563 -166466 -950664 172983 37645 -80742 797573 144438 175462 -121873 -176478 -714701 -645119 -677982 222077 -363093 -551052 148715...
output:
145.0097772360
result:
ok found '145.0097772', expected '145.0097772', error '0.0000000'
Test #19:
score: 0
Accepted
time: 4900ms
memory: 397412kb
input:
250 3693 9045 3805 1961 9287 5288 -6529 -3751 3611 -4955 1110 -9510 8178 9660 2481 9133 4711 -822 5794 -4424 -3374 4932 9638 9647 4293 -3952 -1703 3065 -6545 1336 738 9677 -243 -1729 -5946 -5708 -9996 -8622 -6586 -2082 2480 4 3105 8519 420 6380 -7349 -2302 -1872 -4054 1959 -4783 4400 -3676 -4878 -30...
output:
388.9436034338
result:
ok found '388.9436034', expected '388.9436034', error '0.0000000'
Test #20:
score: 0
Accepted
time: 4846ms
memory: 397640kb
input:
250 961822 144657 -919115 -298876 -971841 -850551 -8328 -120425 758135 361158 -229246 541609 -54684 -528701 455377 -783260 -332531 -202924 -416393 -990497 296199 801812 989528 -515050 800556 719975 860428 596049 546360 -398451 -548518 -239670 784117 -351745 -307726 965794 334556 -597209 741562 75871...
output:
281.5271026368
result:
ok found '281.5271026', expected '281.5271026', error '0.0000000'
Test #21:
score: 0
Accepted
time: 4871ms
memory: 397780kb
input:
250 -480491 -551298 -637223 -268146 -424322 622688 -905391 -762438 617172 -750062 792146 -4478 -710266 594597 624584 -417880 675962 850019 -756658 795092 -287109 -317341 436746 427896 -398057 542221 811077 372972 -362428 -587087 373566 -129535 181207 -92687 402754 -393048 -30175 440303 -431914 -6862...
output:
328.2431164456
result:
ok found '328.2431164', expected '328.2431164', error '0.0000000'
Test #22:
score: 0
Accepted
time: 4896ms
memory: 397596kb
input:
250 -127758 964590 -6321 614577 313086 -538290 -797660 883572 65902 -35917 -480017 -278594 -58648 -47263 775414 582136 577208 67385 655359 284066 274882 123490 141242 600130 137995 -447095 618209 -931278 302525 -367615 980295 -3794 -300900 -615275 -990439 -339280 -748145 264029 -610534 330905 987064...
output:
288.9256005056
result:
ok found '288.9256005', expected '288.9256005', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 8844kb
input:
10 -500 9 -482 8 -437 7 -366 6 -279 5 -170 4 -41 3 117 2 294 1 500 0
output:
8.4778678450
result:
ok found '8.4778678', expected '8.4778678', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 8940kb
input:
10 -1000000 9 -955362 8 -866715 7 -733524 6 -555815 5 -333297 4 -66243 3 245223 2 600624 1 999998 0
output:
8.7902444520
result:
ok found '8.7902445', expected '8.7902445', error '0.0000000'
Test #25:
score: 0
Accepted
time: 10ms
memory: 9680kb
input:
30 -2000 29 -1993 28 -1975 27 -1944 26 -1903 25 -1851 24 -1792 23 -1727 22 -1652 21 -1568 20 -1476 19 -1376 18 -1264 17 -1142 16 -1009 15 -863 14 -711 13 -555 12 -390 11 -216 10 -32 9 165 8 368 7 577 6 794 5 1018 4 1250 3 1489 2 1738 1 1997 0
output:
31.9700998833
result:
ok found '31.9700999', expected '31.9700999', error '0.0000000'
Test #26:
score: 0
Accepted
time: 6ms
memory: 9424kb
input:
30 -1000000 29 -995405 28 -986220 27 -972393 26 -953994 25 -930868 24 -903234 23 -870959 22 -834070 21 -792535 20 -746439 19 -695756 18 -640451 17 -580557 16 -516108 15 -446937 14 -373253 13 -295030 12 -212204 11 -124851 10 -32912 9 63624 8 164860 7 270583 6 380738 5 495436 4 614693 3 738593 2 86700...
output:
32.9031901228
result:
ok found '32.9031901', expected '32.9031901', error '0.0000000'
Test #27:
score: 0
Accepted
time: 64ms
memory: 14068kb
input:
60 -5000 59 -4997 58 -4986 57 -4970 56 -4948 55 -4923 54 -4891 53 -4853 52 -4810 51 -4760 50 -4705 49 -4648 48 -4583 47 -4515 46 -4440 45 -4359 44 -4272 43 -4179 42 -4078 41 -3972 40 -3861 39 -3742 38 -3616 37 -3485 36 -3350 35 -3208 34 -3061 33 -2907 32 -2748 31 -2584 30 -2415 29 -2240 28 -2058 27 ...
output:
71.8095007562
result:
ok found '71.8095008', expected '71.8095008', error '0.0000000'
Test #28:
score: 0
Accepted
time: 56ms
memory: 13620kb
input:
60 -1000000 59 -998938 58 -996753 57 -993433 56 -989018 55 -983454 54 -976758 53 -968906 52 -959936 51 -949821 50 -938590 49 -926218 48 -912763 47 -898176 46 -882440 45 -865575 44 -847621 43 -828533 42 -808352 41 -786949 40 -764409 39 -740717 38 -715970 37 -690117 36 -663118 35 -634993 34 -605708 33...
output:
75.1855261427
result:
ok found '75.1855261', expected '75.1855261', error '0.0000000'
Test #29:
score: 0
Accepted
time: 294ms
memory: 40016kb
input:
100 -20000 99 -19994 98 -19980 97 -19959 96 -19933 95 -19898 94 -19858 93 -19805 92 -19748 91 -19678 90 -19603 89 -19522 88 -19433 87 -19337 86 -19235 85 -19125 84 -19009 83 -18884 82 -18748 81 -18596 80 -18433 79 -18264 78 -18085 77 -17902 76 -17707 75 -17501 74 -17288 73 -17072 72 -16849 71 -16622...
output:
134.6770261829
result:
ok found '134.6770262', expected '134.6770262', error '0.0000000'
Test #30:
score: 0
Accepted
time: 294ms
memory: 40080kb
input:
100 -1000000 99 -999576 98 -998726 97 -997491 96 -995876 95 -993844 94 -991403 93 -988570 92 -985331 91 -981708 90 -977678 89 -973256 88 -968471 87 -963274 86 -957651 85 -951668 84 -945301 83 -938531 82 -931329 81 -923711 80 -915673 79 -907256 78 -898408 77 -889160 76 -879505 75 -869408 74 -858899 7...
output:
138.9839975883
result:
ok found '138.9839976', expected '138.9839976', error '0.0000000'
Test #31:
score: 0
Accepted
time: 1030ms
memory: 150768kb
input:
150 -40000 149 -39984 148 -39960 147 -39926 146 -39886 145 -39839 144 -39784 143 -39722 142 -39647 141 -39565 140 -39480 139 -39389 138 -39290 137 -39181 136 -39063 135 -38936 134 -38800 133 -38655 132 -38498 131 -38334 130 -38163 129 -37985 128 -37797 127 -37601 126 -37399 125 -37193 124 -36979 123...
output:
228.6693055851
result:
ok found '228.6693056', expected '228.6693056', error '0.0000000'
Test #32:
score: 0
Accepted
time: 1059ms
memory: 149824kb
input:
150 -1000000 149 -999832 148 -999483 147 -998973 146 -998277 145 -997405 144 -996353 143 -995120 142 -993712 141 -992141 140 -990389 139 -988460 138 -986361 137 -984063 136 -981574 135 -978908 134 -976051 133 -973002 132 -969790 131 -966386 130 -962811 129 -959055 128 -955095 127 -950958 126 -946662...
output:
223.9682054057
result:
ok found '223.9682054', expected '223.9682054', error '0.0000000'
Test #33:
score: 0
Accepted
time: 2483ms
memory: 258136kb
input:
200 -100000 199 -99990 198 -99973 197 -99950 196 -99917 195 -99878 194 -99828 193 -99773 192 -99709 191 -99634 190 -99550 189 -99451 188 -99339 187 -99218 186 -99087 185 -98945 184 -98797 183 -98640 182 -98472 181 -98295 180 -98109 179 -97914 178 -97705 177 -97484 176 -97249 175 -97010 174 -96763 17...
output:
309.8997066495
result:
ok found '309.8997066', expected '309.8997066', error '0.0000000'
Test #34:
score: 0
Accepted
time: 2492ms
memory: 258176kb
input:
200 -1000000 199 -999897 198 -999689 197 -999374 196 -998967 195 -998474 194 -997877 193 -997165 192 -996352 191 -995436 190 -994426 189 -993339 188 -992161 187 -990877 186 -989482 185 -987987 184 -986391 183 -984702 182 -982913 181 -981041 180 -979052 179 -976962 178 -974758 177 -972459 176 -970050...
output:
314.9777466520
result:
ok found '314.9777467', expected '314.9777467', error '0.0000000'
Test #35:
score: 0
Accepted
time: 4932ms
memory: 396944kb
input:
250 -100000 249 -99996 248 -99985 247 -99964 246 -99936 245 -99902 244 -99859 243 -99808 242 -99751 241 -99688 240 -99618 239 -99539 238 -99456 237 -99363 236 -99266 235 -99166 234 -99062 233 -98951 232 -98833 231 -98710 230 -98586 229 -98453 228 -98315 227 -98169 226 -98017 225 -97859 224 -97695 22...
output:
399.4986320702
result:
ok found '399.4986321', expected '399.4986321', error '0.0000000'
Test #36:
score: 0
Accepted
time: 4891ms
memory: 396396kb
input:
250 -1000000 249 -999934 248 -999801 247 -999608 246 -999369 245 -999064 244 -998687 243 -998240 242 -997733 241 -997171 240 -996542 239 -995856 238 -995110 237 -994305 236 -993438 235 -992507 234 -991500 233 -990427 232 -989296 231 -988091 230 -986826 229 -985493 228 -984101 227 -982644 226 -981122...
output:
408.8274918681
result:
ok found '408.8274919', expected '408.8274919', error '0.0000000'
Test #37:
score: 0
Accepted
time: 4849ms
memory: 397636kb
input:
250 1012 -227 343 -992 1002 -87 -870 555 873 591 -1086 -60 -803 749 -929 -519 295 968 -1029 95 -294 1013 584 -900 -396 -958 -409 -999 -593 -825 -1027 293 -779 640 527 916 -477 -966 996 210 998 -445 -368 961 -979 -406 -524 956 -1049 253 453 932 -139 -1021 -133 1065 -1046 -267 -1023 -95 928 532 -654 7...
output:
193.4349790772
result:
ok found '193.4349791', expected '193.4349791', error '0.0000000'
Test #38:
score: 0
Accepted
time: 4831ms
memory: 397188kb
input:
250 143722 184230 33550 199545 137314 167619 -96577 141269 -175447 -90690 -126133 -202209 154014 -114996 -11150 206860 -162751 -119108 -150322 -146422 -99463 203849 27378 -168853 187084 22360 33621 -206197 -143732 -174287 159 -206512 117429 -182707 137058 110908 -171210 136526 -159473 -158095 148141...
output:
212.9990280254
result:
ok found '212.9990280', expected '212.9990280', error '0.0000000'
Test #39:
score: 0
Accepted
time: 4821ms
memory: 397452kb
input:
250 626626 -779312 605865 -795564 -842260 539064 950763 -309899 -986761 -162159 -926795 -375562 -920043 -391795 -978775 -204924 -644497 -764602 -942293 -334762 -363961 931403 -50677 -998707 970402 -241482 433787 -901012 -715392 698714 781225 -624237 999951 8890 -962735 270436 951222 308490 69224 997...
output:
42.3916120159
result:
ok found '42.3916120', expected '42.3916120', error '0.0000000'
Test #40:
score: 0
Accepted
time: 5040ms
memory: 397036kb
input:
250 -158942 -61 304876 67 -596092 -66 482844 -44 -633328 -34 593703 44 -661509 71 -968180 7 778353 1 -521475 -30 -209606 43 -42053 -71 441684 47 -766779 54 -807390 45 -195820 8 -837797 -45 951843 -3 317166 68 -33704 53 -622182 -68 -138675 -35 698606 -57 -729950 33 407461 -13 932774 48 460886 20 5788...
output:
33.0801914586
result:
ok found '33.0801915', expected '33.0801915', error '0.0000000'
Test #41:
score: 0
Accepted
time: 5039ms
memory: 397840kb
input:
250 708342 124876 -80512 -14220 -540152 -95184 111356 19595 603631 106367 510458 89950 521299 91899 -503279 -88795 809350 142772 290612 51198 430591 75979 862973 152111 117294 20734 351214 61926 973724 171716 -605879 -106803 701401 123625 51040 8947 514762 90746 844509 148860 -110074 -19414 -647623 ...
output:
21.8110297327
result:
ok found '21.8110297', expected '21.8110298', error '0.0000000'
Test #42:
score: 0
Accepted
time: 5056ms
memory: 397880kb
input:
250 -36423 -36391 376553 376573 -608729 -608720 -92032 -92056 -706801 -706896 -139665 -139621 161123 161061 177889 177953 -62927 -62954 294950 295021 625107 625175 -706461 -706468 -691351 -691427 17510 17472 58280 58375 -415119 -415018 -214773 -214749 -349385 -349456 269764 269788 -286580 -286478 -6...
output:
22.1496892597
result:
ok found '22.1496893', expected '22.1496893', error '0.0000000'
Test #43:
score: 0
Accepted
time: 5056ms
memory: 397728kb
input:
250 55 573829 -14 631752 -64 858230 -25 197383 -60 -282104 -59 -751316 -1 -550029 59 814047 -29 -667326 -21 627945 62 517683 -38 242783 -25 953304 60 -46838 -1 -667346 68 -438210 -37 647066 -43 -334803 -40 -431209 -17 -129153 -28 828537 23 864960 52 -212667 -8 539728 -32 -692614 -65 742212 -29 -5901...
output:
22.8372773507
result:
ok found '22.8372774', expected '22.8372774', error '0.0000000'
Test #44:
score: 0
Accepted
time: 5065ms
memory: 397900kb
input:
250 110181 -624551 120920 -685980 97225 -551019 135896 -770962 79288 -449606 120040 -681113 76344 -433072 -40239 227871 -91741 520483 -74254 420892 44816 -254592 16454 -93431 148766 -843459 40657 -230618 -41985 237995 88737 -503000 -26845 152473 -131441 745296 -94734 537210 138467 -785413 -173125 98...
output:
17.4040898665
result:
ok found '17.4040899', expected '17.4040899', error '0.0000000'
Test #45:
score: 0
Accepted
time: 4642ms
memory: 396200kb
input:
250 7735 -743271 -162493 -185341 -8634 968279 740236 -501470 -332764 -553470 -120802 -788998 -8302 968847 -472452 -748840 -715302 -872153 -440493 113659 7176 -743284 875366 -263721 -697824 -612284 -332258 -553224 -423824 -144284 -341287 -327384 -595668 -234804 138735 -525271 -595645 -234042 -715158 ...
output:
137.5248268652
result:
ok found '137.5248269', expected '137.5248269', error '0.0000000'
Test #46:
score: 0
Accepted
time: 4755ms
memory: 396568kb
input:
250 -369729 205979 -278536 125664 -344133 -71646 84554 408373 -374550 204949 -176125 8135 173852 -258661 -280457 126236 414492 18741 -175330 9282 -219033 366207 -279817 128753 -178998 -273067 -126442 253722 83781 408976 415906 17269 -257221 265138 -175328 6160 -370363 201020 -347390 -72083 -130110 2...
output:
298.4506039902
result:
ok found '298.4506040', expected '298.4506040', error '0.0000000'
Test #47:
score: 0
Accepted
time: 4644ms
memory: 396452kb
input:
250 47929 4788 35860 -79527 -120083 117342 -115403 -97704 -143971 -98248 -60199 115628 34357 -103554 -121786 -120977 -146590 132913 159556 131188 -49082 -80931 -89195 46440 -159386 -46652 56567 -82102 -12508 33697 -21236 -95439 -103370 167109 -115468 -97811 130043 16412 -77630 -126093 128659 89028 -...
output:
176.6284116385
result:
ok found '176.6284116', expected '176.6284116', error '0.0000000'
Test #48:
score: 0
Accepted
time: 4608ms
memory: 396884kb
input:
250 827789 421308 106029 -890822 -108874 -140593 354733 -20775 -109751 -137462 177103 -352125 308053 -356605 472446 295377 354739 -20772 545012 633541 -669554 157147 -109757 -137465 -540611 -361342 -136729 299596 -555911 593728 888973 -453205 -555917 593725 -619449 -324104 -447984 317437 -181249 -33...
output:
181.1215200390
result:
ok found '181.1215200', expected '181.1215200', error '0.0000000'
Test #49:
score: 0
Accepted
time: 4827ms
memory: 397016kb
input:
250 936092 353880 784375 -657402 86466 944543 177185 -867808 326305 108607 983092 -586120 -707695 907607 -390625 329598 984305 -502393 795092 447880 173375 -892402 929185 119192 43092 -915120 -625625 376598 737375 141598 697466 850543 466092 -727120 -708908 635880 -101534 850543 -61625 940598 467305...
output:
383.2345363147
result:
ok found '383.2345363', expected '383.2345363', error '0.0000000'
Test #50:
score: 0
Accepted
time: 4789ms
memory: 396552kb
input:
250 -118569 -140749 -97422 -138838 -97375 -138627 -26090 118921 206869 -128921 -97404 -139079 -97033 -139104 206798 -128463 -25769 119134 -96894 -138968 172814 6500 206910 -128995 172798 6616 207159 -128601 -119198 -140960 206410 -128494 173240 6756 206512 -129116 -26002 119194 173478 6701 -96966 -1...
output:
67.5759896055
result:
ok found '67.5759896', expected '67.5759896', error '0.0000000'
Test #51:
score: 0
Accepted
time: 4778ms
memory: 397408kb
input:
250 -229871 727747 503120 660957 279164 -642944 148490 355617 503129 660947 503155 660921 -229877 727747 586885 348612 503158 660957 503149 660944 503149 660954 148484 355635 503120 660944 148518 355612 279174 -642926 586892 348602 -229854 727758 279181 -642939 -229865 727724 503138 660927 279187 -6...
output:
273.9749093956
result:
ok found '273.9749094', expected '273.9749094', error '0.0000000'
Test #52:
score: 0
Accepted
time: 4835ms
memory: 397928kb
input:
250 -448301 -23731 -757738 -414145 -826693 9197 -780743 -422219 -364443 -750631 -796220 -399015 -733092 -418855 -429839 -7644 -444665 -734294 -742340 -386318 -894763 83520 -617532 -849423 -733014 -417877 -789839 -367644 -440192 -765342 -420743 -62219 -394340 -50750 -429665 -46226 -890192 44658 -8410...
output:
183.1873980915
result:
ok found '183.1873981', expected '183.1873981', error '0.0000000'
Test #53:
score: 0
Accepted
time: 0ms
memory: 9116kb
input:
10 -929 -967 -970 -298 -965 360 -958 923 -296 -957 -337 -342 -311 292 -281 975 342 -955 283 -276
output:
19.8182749094
result:
ok found '19.8182749', expected '19.8182749', error '0.0000000'
Test #54:
score: 0
Accepted
time: 288ms
memory: 40132kb
input:
100 -994805 -999938 -996110 -782089 -992919 -573100 -995504 -360728 -992492 -155059 -999396 58200 -995106 269969 -996198 485840 -992862 691285 -999137 905512 -782070 -995961 -787601 -782785 -787156 -575414 -786172 -359796 -781311 -153646 -783933 63971 -783933 274829 -781370 480656 -787605 691837 -78...
output:
859.5346034145
result:
ok found '859.5346034', expected '859.5346034', error '0.0000000'
Test #55:
score: 0
Accepted
time: 1027ms
memory: 149156kb
input:
150 -998502 -999099 -999398 -839150 -998946 -682207 -999717 -523880 -997476 -365420 -999676 -208175 -998634 -47490 -997463 108832 -999252 267688 -998303 427690 -999727 584993 -998548 743468 -997534 902770 -838514 -998825 -838915 -839245 -838761 -681004 -840029 -522233 -841142 -366005 -841333 -207461...
output:
1631.7295261343
result:
ok found '1631.7295261', expected '1631.7295261', error '0.0000000'
Test #56:
score: 0
Accepted
time: 2488ms
memory: 258384kb
input:
200 -998883 -999122 -999739 -863888 -998648 -728163 -998654 -592077 -998857 -456655 -999478 -320991 -999687 -184933 -999447 -49787 -999310 85778 -999163 221451 -999121 358265 -999827 493143 -999266 629360 -999588 765471 -999945 900699 -864070 -998957 -862933 -863164 -863564 -728065 -863308 -591976 -...
output:
2556.7563001614
result:
ok found '2556.7563002', expected '2556.7563002', error '0.0000000'
Test #57:
score: 0
Accepted
time: 4919ms
memory: 397664kb
input:
250 -999494 -999544 -999973 -872086 -999464 -745600 -999441 -619250 -999738 -492789 -998888 -365897 -999365 -239432 -999677 -112880 -999626 13457 -999460 140280 -998934 267634 -999098 393706 -999720 520895 -999132 647797 -999369 774589 -998920 900467 -872613 -999663 -873317 -872283 -873066 -746144 -...
output:
3597.9060013911
result:
ok found '3597.9060014', expected '3597.9060014', error '0.0000000'