QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479628 | #1196. Fun Region | crimson231 | AC ✓ | 18ms | 4064kb | C++14 | 8.8kb | 2024-07-15 19:36:30 | 2024-07-15 19:36:30 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <deque>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld INF = 1e17;
const ld TOL = 1e-10;
const ld PI = acos(-1);
const int LEN = 2e3 + 5;
bool zero(const ld& x) { return std::abs(x) < TOL; }
int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
int N;
struct Pos {
ld x, y;
Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
bool operator != (const Pos& p) const { return !zero(x - p.x) || !zero(y - p.y); }
bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
ld operator * (const Pos& p) const { return { x * p.x + y * p.y }; }
ld operator / (const Pos& p) const { return { x * p.y - y * p.x }; }
Pos operator - () const { return { -x, -y }; }
Pos operator ~ () const { return { -y, x }; }
ld Euc() const { return x * x + y * y; }
ld mag() const { return sqrt(Euc()); }
Pos unit() const { return *this / mag(); }
ld rad() const { return atan2(y, x); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = { 0, 0 };
typedef std::vector<Pos> Polygonf;
struct Linear {//ps[0] -> ps[1] :: refer to bulijiojiodibuliduo
Pos ps[2];
Pos dir_;
Pos& operator[](int i) { return ps[i]; }
Pos dir() const { return dir_; }
Linear(Pos a = Pos(0, 0), Pos b = Pos(0, 0)) {
ps[0] = a;
ps[1] = b;
dir_ = (ps[1] - ps[0]).unit();
}
bool include(const Pos& p) const { return sign(dir_ / (p - ps[0])) > 0; }
friend bool parallel(const Linear& l0, const Linear& l1) { return zero(l0.dir() / l1.dir()); }
friend bool same_dir(const Linear& l0, const Linear& l1) { return parallel(l0, l1) && l0.dir() * l1.dir() > 0; }
bool operator < (const Linear& l0) const {
if (same_dir(*this, l0)) return l0.include(ps[0]);
else return cmpq(this->dir(), l0.dir());
}
//bool operator == (const Linear& l0) const {
// return ps[0] == l0.ps[0] && ps[1] == l0.ps[1] && dir_ == l0.dir_;
//}
};
typedef std::vector<Linear> VHP;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = cross(d1, d2, d3); return sign(ret); }
Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) { ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2); return (p1 * a2 + p2 * a1) / (a1 + a2); }
Pos intersection(Linear& l1, Linear& l2) { return intersection(l1[0], l1[1], l2[0], l2[1]); }
std::vector<Pos> half_plane_intersection(std::vector<Linear>& HP) {//refer to bulijiojiodibuliduo
auto check = [&](Linear& u, Linear& v, Linear& w) -> bool {
return w.include(intersection(u, v));
};
std::sort(HP.begin(), HP.end());
//HP.erase(unique(HP.begin(), HP.end()), HP.end());
std::deque<Linear> dq;
int sz = HP.size();
for (int i = 0; i < sz; ++i) {
if (i && same_dir(HP[i], HP[(i - 1) % sz])) continue;
while (dq.size() > 1 && !check(dq[dq.size() - 2], dq[dq.size() - 1], HP[i])) dq.pop_back();
while (dq.size() > 1 && !check(dq[1], dq[0], HP[i])) dq.pop_front();
dq.push_back(HP[i]);
}
while (dq.size() > 2 && !check(dq[dq.size() - 2], dq[dq.size() - 1], dq[0])) dq.pop_back();
while (dq.size() > 2 && !check(dq[1], dq[0], dq[dq.size() - 1])) dq.pop_front();
sz = dq.size();
if (sz < 3) return {};
std::vector<Pos> HPI;
for (int i = 0; i < sz; ++i) HPI.push_back(intersection(dq[i], dq[(i + 1) % sz]));
return HPI;
}
ld area(const Polygonf& H) {
Pos pivot = Pos(0, 0);
ld ret = 0;
int h = H.size();
for (int i = 0; i < h; i++) {
const Pos& cur = H[i], & nxt = H[(i + 1) % h];
ret += cross(pivot, cur, nxt);
}
return ret * .5;
}
struct Pii {
int x, y;
int i;
Pii(int X = 0, int Y = 0) : x(X), y(Y) { i = -1; }
bool operator == (const Pii& p) const { return x == p.x && y == p.y; }
bool operator != (const Pii& p) const { return x != p.x || y != p.y; }
bool operator < (const Pii& p) const { return x == p.x ? y < p.y : x < p.x; }
Pii operator + (const Pii& p) const { return { x + p.x, y + p.y }; }
Pii operator - (const Pii& p) const { return { x - p.x, y - p.y }; }
Pii operator * (const int& n) const { return { x * n, y * n }; }
Pii operator / (const int& n) const { return { x / n, y / n }; }
ll operator * (const Pii& p) const { return { (ll)x * p.x + (ll)y * p.y }; }
ll operator / (const Pii& p) const { return { (ll)x * p.y - (ll)y * p.x }; }
friend std::istream& operator >> (std::istream& is, Pii& p) { is >> p.x >> p.y; return is; }
friend std::ostream& operator << (std::ostream& os, const Pii& p) { os << p.x << " " << p.y; return os; }
};
typedef std::vector<Pii> Polygon;
ll cross(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) / (d3 - d2); }
ll dot(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) * (d3 - d2); }
int ccw(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
bool on_seg_strong(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && ret >= 0; }
bool inner_check(Pii d1, Pii d2, Pii d3, const Pii& t) {
if (ccw(d1, d2, d3) < 0) std::swap(d2, d3);
return ccw(d1, d2, t) > 0 && ccw(d2, d3, t) > 0 && ccw(d3, d1, t) > 0;
}
ll area(const Polygon& H) {
Pii pivot = Pii(0, 0);
ld ret = 0;
int h = H.size();
for (int i = 0; i < h; i++) {
const Pii& cur = H[i], & nxt = H[(i + 1) % h];
ret += cross(pivot, cur, nxt);
}
return ret;
}
void norm(Polygon& H, const bool& f = 1) {
if (f && area(H) < 0) std::reverse(H.begin(), H.end());//ccw
if (!f && area(H) > 0) std::reverse(H.begin(), H.end());//cw
return;
}
Pos P(const Pii& p) { return Pos(p.x, p.y); }
Pii P(const Pos& p) { return Pii(p.x, p.y); }
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(15);
std::cin >> N;
Polygon H(N);
for (Pii& p : H) std::cin >> p;
norm(H, 0);//cw
//convex
bool f = 1;
for (int i = 0; i < N; i++) {
Pii& pre = H[(i - 1 + N) % N], & cur = H[i], & nxt = H[(i + 1) % N];
int CCW = ccw(pre, cur, nxt);
assert(CCW);
if (CCW > 0) { f = 0; }
}
if (f) { std::cout << std::abs(area(H)) * .5 << "\n"; return; }
//convex
//concave
for (int i = 0; i < N; i++) {
Pii& pre = H[(i - 1 + N) % N], & cur = H[i], & nxt = H[(i + 1) % N];
if (ccw(pre, cur, nxt) < 0) continue;
//if (ccw(pre, cur, nxt) > 0);
Pii& nnxt = H[(i + 2) % N];
if (ccw(cur, nxt, nnxt) > 0) continue;
int j;
for (j = (i + 2) % N; j != (i - 1 + N) % N; j = (j + 1) % N) {
int j2 = (j + 1) % N;
if (!ccw(cur, nxt, H[j2]) ||
(ccw(cur, nxt, H[j]) != ccw(cur, nxt, H[j2]))) {
break;
}
}
cur.i = (j + 1) % N;
for (int k = (i + 2) % N; k != (j + 1) % N; k = (k + 1) % N) {
int k1 = (k + 1) % N;
if (ccw(cur, nxt, H[k]) > 0 ||
on_seg_strong(cur, H[k], nxt) ||
inner_check(cur, H[k], H[k1], nxt)) {
cur.i = -1;
break;
}
}
}
VHP vhp;
for (int i = 0; i < N; i++) {
if (H[i].i == -1) continue;
Pii& cur = H[i], & nxt = H[(i + 1) % N];
vhp.push_back(Linear(P(nxt), P(cur)));
int j, k = -1;
for (j = (i + 2) % N; j != cur.i; j = (j + 1) % N) {
if (H[j].i != -1) {
k = j;
break;
}
}
if (k == -1) {
for (j = (i + 1) % N; j != cur.i; j = (j + 1) % N) {
int j2 = (j + 1) % N;
vhp.push_back(Linear(P(H[j2]), P(H[j])));
}
}
else {
int k1 = (k + 1) % N;
for (j = (i + 1) % N; j != k; j = (j + 1) % N) {
assert(H[j].i == -1);
int j2 = (j + 1) % N;
int ccw1 = ccw(H[k], H[k1], H[j]);
int ccw2 = ccw(H[k], H[k1], H[j2]);
if (ccw1 == -1 && ccw2 == -1) {
vhp.push_back(Linear(P(H[j2]), P(H[j])));
}
else if ((ccw1 == -1 || ccw2 == -1) && inner_check(H[k1], H[j], H[j2], H[k])) {
vhp.push_back(Linear(P(H[j2]), P(H[j])));
break;
}
}
}
}
Polygonf hpi = half_plane_intersection(vhp);
std::cout << area(hpi) << "\n";
return;
}
int main() { solve(); return 0; }//boj18219 ICPC 2019 Asia Yokohama Regional J Fun Region
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
4 10 0 20 10 10 30 0 10
output:
300.000000000000000
result:
ok found '300.0000000', expected '300.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
10 145 269 299 271 343 193 183 139 408 181 356 324 176 327 147 404 334 434 102 424
output:
12658.313019131075635
result:
ok found '12658.3130191', expected '12658.3130191', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
6 144 401 297 322 114 282 372 178 197 271 368 305
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 12ms
memory: 3960kb
input:
2000 9274 7020 6000 7020 6000 7030 8801 7030 8801 7040 6000 7040 6000 7050 6517 7050 6517 7060 6000 7060 6000 7070 6182 7070 6182 7080 6000 7080 6000 7090 9928 7090 9928 7100 6000 7100 6000 7110 8928 7110 8928 7120 6000 7120 6000 7130 7778 7130 7778 7140 6000 7140 6000 7150 8627 7150 8627 7160 6000 ...
output:
80000.000000000000000
result:
ok found '80000.0000000', expected '80000.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
32 6000 9970 8929 9970 8929 9980 6000 9980 6000 9990 8806 9990 8806 10000 4000 10000 4000 60 3819 50 3819 40 4000 40 4000 30 323 30 323 20 4000 20 4000 10 1367 10 1367 0 6000 0 6000 9910 6139 9910 6139 9920 6000 9920 6000 9930 8225 9930 8225 9940 6000 9940 6000 9950 9296 9950 9296 9960 6000 9960
output:
19760000.000000000000000
result:
ok found '19760000.0000000', expected '19760000.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 18ms
memory: 3992kb
input:
1859 2843 492 2851 488 2866 481 2909 461 2940 447 2964 436 2975 431 2987 425 2995 422 2998 421 2999 420 3040 403 3054 397 3059 395 3059 394 3066 392 3073 389 3075 387 3076 388 3078 386 3092 381 3109 373 3126 367 3134 364 3145 359 3149 358 3163 352 3173 348 3174 348 3180 345 3203 336 3211 333 3217 33...
output:
2079546.000000000000000
result:
ok found '2079546.0000000', expected '2079546.0000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 18ms
memory: 4024kb
input:
1844 9223 2327 9225 2330 9231 2340 9233 2343 9234 2344 9238 2350 9263 2392 9264 2393 9268 2399 9279 2417 9280 2419 9298 2451 9302 2457 9305 2461 9327 2498 9357 2552 9365 2566 9367 2568 9368 2571 9379 2591 9386 2603 9398 2626 9408 2644 9413 2655 9418 2663 9431 2689 9436 2698 9451 2728 9462 2749 9469 ...
output:
1418060.000000000000000
result:
ok found '1418060.0000000', expected '1418060.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 18ms
memory: 3912kb
input:
1861 5509 29 5515 29 5550 33 5559 33 5578 36 5601 38 5612 40 5676 48 5686 49 5687 50 5689 50 5696 51 5699 52 5709 52 5722 55 5724 55 5745 58 5761 60 5763 60 5791 65 5798 66 5814 69 5819 69 5903 84 5913 86 5916 87 5941 92 5965 97 5974 98 5979 99 5986 100 5995 102 6038 111 6048 113 6050 114 6051 114 6...
output:
1027161.000000000000000
result:
ok found '1027161.0000000', expected '1027161.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 18ms
memory: 3924kb
input:
1835 680 7513 663 7483 654 7468 651 7461 648 7457 643 7448 630 7425 614 7395 602 7373 600 7371 596 7363 577 7328 570 7313 560 7295 544 7262 539 7253 536 7248 517 7208 516 7206 512 7199 510 7195 499 7172 480 7132 468 7108 453 7075 453 7074 438 7039 437 7039 433 7031 415 6988 412 6984 409 6975 408 697...
output:
13822236.000000000000000
result:
ok found '13822236.0000000', expected '13822236.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 18ms
memory: 3932kb
input:
1858 9984 5375 9983 5383 9981 5413 9981 5418 9979 5441 9978 5446 9977 5459 9974 5485 9972 5503 9972 5514 9971 5514 9969 5535 9969 5536 9965 5570 9964 5585 9955 5656 9952 5678 9950 5691 9948 5701 9946 5720 9945 5723 9945 5725 9944 5731 9941 5757 9939 5767 9935 5790 9935 5791 9930 5820 9929 5830 9927 ...
output:
2490324.500000000000000
result:
ok found '2490324.5000000', expected '2490324.5000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
20 2340 769 3619 197 3795 149 5653 45 6914 383 7134 480 8823 1781 8989 1989 9211 2308 9332 2507 9781 3542 9828 3709 9859 3830 9925 4147 9916 5905 772 2336 1565 1370 1853 1118 1864 1109 2045 969
output:
29346414.000000000000000
result:
ok found '29346414.0000000', expected '29346414.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
216 9573 7015 9508 7159 9409 7352 9380 7407 9371 7424 9321 7511 9294 7558 9275 7590 9270 7598 9180 7739 9112 7841 9075 7894 8977 8027 8913 8109 8797 8250 8780 8269 8704 8355 8640 8425 8612 8454 8596 8470 8594 8473 8560 8507 8479 8589 8431 8634 8372 8689 8340 8718 8105 8916 8034 8971 7977 9015 7840 9...
output:
36377905.149990767240524
result:
ok found '36377905.1499908', expected '36377905.1499908', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
406 8048 1039 8053 1043 8176 1141 8299 1247 8324 1267 8352 1293 8379 1318 8416 1351 8422 1358 8472 1405 8479 1412 8499 1431 8510 1443 8517 1448 8517 1449 8563 1496 8606 1540 8616 1551 8664 1601 8673 1610 8686 1625 8703 1643 8744 1689 8755 1701 8763 1711 8785 1737 8797 1750 8928 1910 8951 1939 8982 1...
output:
20479513.012126922607422
result:
ok found '20479513.0121269', expected '20479513.0121269', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3912kb
input:
594 4745 8 4753 8 4784 7 4806 6 4836 4 4846 4 4921 3 4986 2 5042 2 5114 4 5120 3 5233 7 5347 14 5350 14 5359 15 5415 19 5427 20 5455 22 5483 25 5493 27 5494 26 5496 27 5515 28 5521 29 5522 29 5587 36 5621 41 5670 47 5674 48 5691 50 5732 56 5802 67 5821 70 5837 73 5843 73 5869 78 5916 87 5953 93 5973...
output:
13084325.895022276788950
result:
ok found '13084325.8950223', expected '13084325.8950223', error '0.0000000'
Test #15:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
774 9982 4596 9983 4615 9983 4619 9984 4624 9984 4627 9985 4645 9988 4680 9989 4700 9993 4765 9995 4823 9995 4826 9996 4851 9996 4884 9997 4896 9997 4922 9998 4993 9998 5000 9997 5086 9997 5105 9996 5116 9997 5117 9996 5157 9995 5158 9995 5162 9992 5236 9992 5250 9991 5257 9989 5288 9987 5327 9983 5...
output:
16822524.668747767806053
result:
ok found '16822524.6687478', expected '16822524.6687478', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
4 0 0 10000 0 10000 10000 0 10000
output:
100000000.000000000000000
result:
ok found '100000000.0000000', expected '100000000.0000000', error '0.0000000'
Test #17:
score: 0
Accepted
time: 16ms
memory: 3912kb
input:
1999 10000 206 1 206 10000 207 1 207 10000 208 1 208 10000 209 1 209 10000 210 1 210 10000 211 1 211 10000 212 1 212 10000 213 1 213 10000 214 1 214 10000 215 1 215 10000 216 1 216 10000 217 1 217 10000 218 1 218 10000 219 1 219 10000 220 1 220 10000 221 1 221 10000 222 1 222 10000 223 1 223 10000 2...
output:
5000.500000000000000
result:
ok found '5000.5000000', expected '5000.5000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 16ms
memory: 3920kb
input:
1999 2558 4070 7558 9067 2555 4075 7555 9072 2552 4080 7552 9077 2549 4085 7549 9082 2546 4090 7546 9087 2543 4095 7543 9092 2540 4100 7540 9097 2537 4105 7537 9102 2534 4110 7534 9107 2531 4115 7531 9112 2528 4120 7528 9117 2525 4125 7525 9122 2522 4130 7522 9127 2519 4135 7519 9132 2516 4140 7516 ...
output:
20015.527544070035219
result:
ok found '20015.5275441', expected '20015.5275441', error '0.0000000'
Test #19:
score: 0
Accepted
time: 12ms
memory: 4000kb
input:
1999 8044 3034 8041 3044 8038 3043 8035 3053 8032 3052 8029 3062 8026 3061 8023 3071 8020 3070 8017 3080 8014 3079 8011 3089 8008 3088 8005 3098 8002 3097 7999 3107 7996 3106 7993 3116 7990 3115 7987 3125 7984 3124 7981 3134 7978 3133 7975 3143 7972 3142 7969 3152 7966 3151 7963 3161 7960 3160 7957 ...
output:
12416.622345803887583
result:
ok found '12416.6223458', expected '12416.6223458', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 1664 1839 5145 767 5644 8714
output:
14099217.500000000000000
result:
ok found '14099217.5000000', expected '14099217.5000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
4 5094 2585 5154 4865 5972 9655 5003 6086
output:
388962.331699395319447
result:
ok found '388962.3316994', expected '388962.3316994', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
5 3839 2462 6450 9731 917 6915 2220 5164 1430 1649
output:
15630841.306313807144761
result:
ok found '15630841.3063138', expected '15630841.3063138', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 4474 1457 4905 3089 7554 5776 6426 6077 4616 4542 3028 1491
output:
3517836.371496747247875
result:
ok found '3517836.3714967', expected '3517836.3714967', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
7 5319 5082 5280 6009 5900 8273 4111 5641 2346 6076 4674 4589 5948 4865
output:
920101.569259552401491
result:
ok found '920101.5692596', expected '920101.5692596', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
8 4096 3756 5382 4371 7186 1749 9632 4602 9758 4704 7149 6803 3563 8911 1013 2622
output:
20333963.765386167913675
result:
ok found '20333963.7653862', expected '20333963.7653862', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
9 7720 2038 8160 2661 6427 4528 7007 5869 7399 6513 2037 4071 995 3028 3176 881 5040 1874
output:
16379711.105319684371352
result:
ok found '16379711.1053197', expected '16379711.1053197', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
10 5757 1393 8096 4772 7059 5458 6743 5903 2827 8013 2719 6272 4013 5299 4392 5065 1849 2006 4954 4503
output:
6259308.473179914057255
result:
ok found '6259308.4731799', expected '6259308.4731799', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
11 6380 2640 6053 3857 8539 3296 7275 6299 6595 7559 5977 7236 2481 7189 1352 7020 2354 6448 3042 3511 5262 3499
output:
2610035.089641427621245
result:
ok found '2610035.0896414', expected '2610035.0896414', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
12 4742 5314 3575 5937 1908 5632 3425 2791 4749 4476 4329 252 7368 4691 8318 6692 8011 7335 5673 5882 4724 6947 3994 8628
output:
474170.161448199534789
result:
ok found '474170.1614482', expected '474170.1614482', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
13 5477 9803 2323 7271 2200 6085 3516 5451 4596 5080 458 5740 1946 3432 5670 1483 5233 4897 6551 6066 5538 5823 5338 6304 5707 9308
output:
631741.317085074726492
result:
ok found '631741.3170851', expected '631741.3170851', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
14 4512 6057 2092 8704 1615 5835 3126 4434 1535 2397 1893 1846 4686 2290 5217 3920 5402 4267 5492 4465 8382 1789 9291 4246 5608 9153 5332 7607
output:
4505176.498228449374437
result:
ok found '4505176.4982284', expected '4505176.4982284', error '0.0000000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
15 4466 5396 1705 4917 3305 4526 1737 3617 3847 4013 5854 2118 5870 2160 6816 2334 7348 1946 6136 4410 8998 4850 9815 5079 7271 8684 6067 9279 5028 6591
output:
2398614.676149465143681
result:
ok found '2398614.6761495', expected '2398614.6761495', error '0.0000000'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
16 2696 3357 3395 2997 3757 2086 4827 84 6762 1878 7658 1889 7639 4233 7259 4355 6253 5691 7394 7382 6070 8938 5062 5341 3877 7728 3529 8177 1772 8147 1581 2562
output:
5453.740360503114061
result:
ok found '5453.7403605', expected '5453.7403605', error '0.0000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
17 9639 5654 8700 7119 6752 8284 6658 9048 6061 9043 5240 6097 5166 6416 5085 8596 4880 5732 3324 8722 3573 6800 2159 7089 3636 5438 4221 4774 3430 1818 5118 257 5178 431
output:
8859629.518314387649298
result:
ok found '8859629.5183144', expected '8859629.5183144', error '0.0000000'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
18 4684 4937 1396 4109 1880 3238 2541 811 3585 601 4837 4007 4735 1936 6971 2430 5309 4810 9367 4665 5106 5027 8195 6885 6551 9079 5139 7637 4917 6186 4783 7309 2686 8721 1754 7471
output:
125428.753615232068114
result:
ok found '125428.7536152', expected '125428.7536152', error '0.0000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
16 5000 4332 4332 5000 5000 5668 5668 5000 5000 1761 1761 5000 5000 8239 8239 5000 8914 5000 5000 8914 1086 5000 5000 1086 8205 5000 5000 8205 1795 5000 5000 1795
output:
6521992.750000000000000
result:
ok found '6521992.7500000', expected '6521992.7500000', error '0.0000000'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
2000 5411 5000 5000 5411 4589 5000 5000 4589 5405 5000 5000 5405 4595 5000 5000 4595 5335 5000 5000 5335 4665 5000 5000 4665 5328 5000 5000 5328 4672 5000 5000 4672 5302 5000 5000 5302 4698 5000 5000 4698 5287 5000 5000 5287 4713 5000 5000 4713 5283 5000 5000 5283 4717 5000 5000 4717 5278 5000 5000 ...
output:
63.000000000000000
result:
ok found '63.0000000', expected '63.0000000', error '0.0000000'
Test #38:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
17 253 449 231 314 60 302 192 231 115 70 230 139 248 89 269 126 304 104 300 141 376 119 332 169 485 216 356 250 464 395 440 408 299 287
output:
2823.585557503602104
result:
ok found '2823.5855575', expected '2823.5855575', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
12 1 0 3 0 3 1 5 1 5 3 4 3 4 5 2 5 2 4 0 4 0 2 1 2
output:
1.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
32 65 44 446 37 456 81 115 82 70 424 417 449 442 152 160 116 117 376 381 399 396 194 208 161 170 333 344 343 364 231 265 216 258 266 321 275 316 293 223 285 237 191 386 217 361 366 153 342 190 141 419 175 401 426 95 395 149 95 471 132 450 474 33 441
output:
15933.326011304447093
result:
ok found '15933.3260113', expected '15933.3260113', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
12 31 458 32 409 82 416 87 196 25 186 36 141 158 144 172 196 125 201 119 421 179 425 176 471
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
43 428 479 366 477 287 466 197 439 157 409 124 364 90 305 60 217 52 147 60 80 98 47 164 30 228 22 324 20 362 27 425 44 457 65 469 89 472 126 457 155 436 172 412 171 393 152 388 120 382 82 351 67 283 66 247 68 208 75 174 85 150 108 134 147 138 195 158 264 184 319 229 371 275 404 326 421 386 423 440 4...
output:
9574.730709476949414
result:
ok found '9574.7307095', expected '9574.7307095', error '0.0000000'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
29 132 465 107 334 123 242 114 128 124 50 165 40 177 88 194 170 186 208 190 273 197 332 189 371 189 412 226 425 285 410 286 364 278 312 241 295 215 294 204 283 200 261 208 238 250 234 319 258 332 301 341 381 317 431 220 471 162 472
output:
16853.803655815285310
result:
ok found '16853.8036558', expected '16853.8036558', error '0.0000000'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
16 204 449 280 336 224 287 210 357 92 346 103 129 248 124 238 239 301 314 352 248 276 176 354 85 492 273 453 324 379 269 227 464
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
76 148 257 231 232 302 197 344 133 331 91 268 61 175 59 126 95 136 139 166 161 240 159 267 126 238 102 197 114 190 133 166 121 170 100 197 86 243 86 281 110 287 143 259 175 179 191 130 162 97 105 113 66 158 36 229 29 348 33 411 75 422 141 394 197 302 260 187 282 98 316 83 387 111 454 232 463 329 460...
output:
11552.254374559051939
result:
ok found '11552.2543746', expected '11552.2543746', error '0.0000000'
Test #46:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
43 369 304 284 263 213 241 151 202 116 156 125 110 161 72 219 61 331 55 393 82 419 139 412 174 383 194 320 201 249 183 241 145 276 131 292 151 319 163 368 145 361 116 301 98 238 98 159 117 178 185 241 218 325 234 432 273 451 334 395 400 275 424 166 418 101 372 89 312 140 275 193 281 206 312 183 316 ...
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #47:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
14 0 0 10 0 20 10 20 0 30 0 30 50 20 50 20 40 0 50 0 40 20 30 0 30 0 20 20 20
output:
225.000000000000000
result:
ok found '225.0000000', expected '225.0000000', error '0.0000000'
Test #48:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
14 80 20 100 20 100 30 80 30 100 40 100 50 80 40 80 50 70 50 70 0 80 0 80 10 90 0 100 0
output:
250.000000000000000
result:
ok found '250.0000000', expected '250.0000000', error '0.0000000'
Test #49:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
6 0 10 10 10 10 0 30 10 20 10 20 20
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #50:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
6 0 0 1731 1971 6924 0 6924 7884 3462 3942 0 7884
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #51:
score: 0
Accepted
time: 11ms
memory: 3844kb
input:
1997 3908 7186 4995 5010 3369 8248 3742 7495 3196 8560 2914 9075 3115 8666 3503 7878 3121 8572 4518 5914 3643 7523 4364 6181 4836 5304 2850 8959 3474 7801 2825 8973 4059 6705 3798 7143 2927 8667 4887 5194 3881 6907 3365 7776 3907 6854 4938 5105 3879 6898 4032 6630 3235 7915 4167 6367 3342 7681 3651 ...
output:
0.000030245953798
result:
ok found '0.0000302', expected '0.0000302', error '0.0000000'
Test #52:
score: 0
Accepted
time: 12ms
memory: 3940kb
input:
2000 5522 5219 8387 6423 8073 6292 5769 5326 5134 5057 7832 6210 9500 6938 5728 5314 6398 5607 8840 6684 8386 6486 5941 5413 6212 5534 7948 6320 7368 6082 7458 6130 8630 6673 5778 5365 8910 6840 6535 5729 8580 6706 7937 6401 9333 7091 6070 5523 6445 5709 6269 5626 5824 5408 9288 7127 8332 6658 8308 ...
output:
0.000211900552731
result:
ok found '0.0002119', expected '0.0002119', error '0.0000000'
Test #53:
score: 0
Accepted
time: 11ms
memory: 4064kb
input:
1998 4932 8589 4943 7827 4968 6473 4913 8891 4991 5372 4950 6812 4959 6459 4939 7033 4981 5633 4921 7622 4894 8476 4998 5063 4949 6492 4965 5978 4910 7511 4936 6785 4926 6948 4943 6363 4971 5676 4923 6712 4968 5705 4918 6801 4816 8882 4873 7459 4998 5038 4962 5706 4746 9708 4954 5844 4807 8476 4787 ...
output:
0.074952258259867
result:
ok found '0.0749523', expected '0.0749523', error '0.0000000'
Test #54:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
50 5015 4997 5093 4991 5022 5000 5037 5000 5087 5022 5009 5003 5006 5003 5042 5050 5055 5070 5047 5061 5003 5005 5036 5079 5010 5022 5011 5040 5006 5065 5000 5047 4993 5029 4957 5077 4986 5025 4954 5075 4962 5044 4916 5032 4929 5026 4962 5001 4933 4995 4987 4999 4978 4992 4959 4972 4964 4973 4942 49...
output:
0.007300534995466
result:
ok found '0.0073005', expected '0.0073005', error '0.0000000'
Test #55:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
79 4986 5084 4986 5070 4985 5072 4985 5049 4995 5016 4972 5076 4969 5083 4970 5075 4988 5024 4983 5031 4963 5063 4980 5034 4961 5065 4967 5055 4975 5040 4942 5080 4956 5053 4944 5063 4973 5028 4932 5068 4998 5002 4952 5046 4991 5008 4976 5021 4991 5007 4933 5044 4993 5004 4952 5027 4960 5021 4961 50...
output:
52.376553770125611
result:
ok found '52.3765538', expected '52.3765538', error '0.0000000'
Test #56:
score: 0
Accepted
time: 10ms
memory: 4060kb
input:
1998 1917 1090 1994 1130 1949 1060 1988 1105 2013 1088 1995 1051 2018 1081 2017 1075 1990 1012 2028 1056 2061 1050 2025 988 2054 1014 2063 1026 2073 1039 2053 1010 2090 1056 2055 1007 2068 984 2114 1039 2077 956 2130 934 2173 939 2184 950 2190 950 2174 925 2199 950 2170 891 2184 905 2217 932 2232 93...
output:
648.916144486771373
result:
ok found '648.9161445', expected '648.9161445', error '0.0000000'
Test #57:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
8 10000 5000 6290 9098 4839 9872 4493 5089 0 5000 1303 4598 6845 4019 9531 4513
output:
19096233.353069297969341
result:
ok found '19096233.3530693', expected '19096233.3530693', error '0.0000000'
Test #58:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
12 9655 4437 10000 5000 7601 7069 7417 5094 6234 9740 5647 5823 2952 9902 0 5000 1077 2483 1484 1006 5194 4762 5906 4669
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #59:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
102 8183 8502 8121 5436 8115 5246 7984 5519 7960 5756 7651 9056 7344 6661 6964 6004 6859 6357 6796 6201 6174 6993 6018 7554 4943 5819 4682 9215 4340 5133 4265 9301 4091 6200 4056 7421 3879 9768 3151 8458 3084 5033 2972 8393 2878 5776 2846 9118 2741 5004 2670 7439 2573 5540 2176 7512 1986 9889 1888 9...
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #60:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
202 7712 8006 7061 5151 7042 5648 6678 6438 6317 5458 6059 6865 5961 6359 5737 6582 5652 8116 5534 8511 5441 8740 5383 6591 5353 6949 5179 9463 5048 8393 5040 7166 4804 6848 4702 7324 4630 5983 4553 5243 4238 8581 4115 5462 4084 7836 4076 8750 4015 7738 4001 7981 3945 9486 3730 5060 3543 9931 3496 6...
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #61:
score: 0
Accepted
time: 3ms
memory: 3976kb
input:
1002 2414 9545 2413 7915 2325 7087 2274 8223 2235 9807 2148 5400 2130 7668 2130 8701 2112 8289 2097 9514 2094 8965 2090 5062 2089 8687 2062 9783 2025 9987 2011 6627 2008 5825 1995 5049 1986 6219 1956 6644 1931 5762 1899 9376 1877 5902 1849 6083 1847 6166 1842 6903 1829 9005 1806 5550 1794 8579 1780 ...
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #62:
score: 0
Accepted
time: 11ms
memory: 4028kb
input:
1995 5769 294 5786 3987 5789 618 5814 35 5831 3023 5840 1612 5853 4924 5902 4849 5910 3592 5928 2236 5944 3280 5946 4848 6003 674 6009 3876 6035 990 6043 1306 6043 3462 6058 2385 6066 1654 6070 3176 6085 623 6090 4658 6097 1213 6115 1672 6115 2000 6129 4063 6130 3879 6148 576 6176 1065 6179 3641 619...
output:
0.000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'