QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408413 | #5046. Moon | crimson231 | RE | 38ms | 10428kb | C++17 | 11.9kb | 2024-05-10 10:46:35 | 2024-05-10 10:46:37 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <random>
#include <cassert>
#include <array>
#include <tuple>
typedef long long ll;
typedef long double ld;
//typedef double ld;
typedef std::pair<int, int> pi;
const ld INF = 1e17;
const ld TOL = 1e-8;
const int LEN = 1e6;
const ld PI = acos(-1);
int N, M, T, Q;
//geometry-struct
inline bool zero(const ld& x) { return std::abs(x) < TOL; }
inline int dcmp(const ld& x) { return std::abs(x) < TOL ? 0 : x > 0 ? 1 : -1; }
struct Pos3D {
ld x, y, z;
Pos3D(ld X = 0, ld Y = 0, ld Z = 0) : x(X), y(Y), z(Z) {}
bool operator == (const Pos3D& p) const { return zero(x - p.x) && zero(y - p.y) && zero(z - p.z); }
bool operator != (const Pos3D& p) const { return !zero(x - p.x) || !zero(y - p.y) || !zero(z - p.z); }
bool operator < (const Pos3D& p) const { return zero(x - p.x) ? zero(y - p.y) ? z < p.z : y < p.y : x < p.x; }
inline ld operator * (const Pos3D& p) const { return x * p.x + y * p.y + z * p.z; }
inline Pos3D operator / (const Pos3D& p) const {
Pos3D ret;
ret.x = y * p.z - z * p.y;
ret.y = z * p.x - x * p.z;
ret.z = x * p.y - y * p.x;
return ret;
}
inline Pos3D operator + (const Pos3D& p) const { return { x + p.x, y + p.y, z + p.z }; }
inline Pos3D operator - (const Pos3D& p) const { return { x - p.x, y - p.y, z - p.z }; }
inline Pos3D operator * (const ld& scalar) const { return { x * scalar, y * scalar, z * scalar }; }
inline Pos3D operator / (const ld& scalar) const { return { x / scalar, y / scalar, z / scalar }; }
Pos3D& operator += (const Pos3D& p) { x += p.x; y += p.y; z += p.z; return *this; }
Pos3D& operator -= (const Pos3D& p) { x -= p.x; y -= p.y; z -= p.z; return *this; }
Pos3D& operator *= (const ld& scalar) { x *= scalar; y *= scalar; z *= scalar; return *this; }
Pos3D& operator /= (const ld& scalar) { x /= scalar; y /= scalar; z /= scalar; return *this; }
inline ld Euc() const { return x * x + y * y + z * z; }
inline ld mag() const { return sqrtl(Euc()); }
ld lon() const { return atan2(y, x); }
ld lat() const { return atan2(z, sqrtl(x * x + y * y)); }
inline Pos3D unit() const { return *this / mag(); }
inline Pos3D norm(const Pos3D& p) const { return (*this / p).unit(); }
Pos3D rotate(const ld& th, const Pos3D& axis) const {
ld SIN = sin(th), COS = cos(th);
Pos3D u = axis.unit();
return u * (*this * u) * (1 - COS) + (*this * COS) - (*this / u) * SIN;
}
inline friend std::istream& operator >> (std::istream& is, Pos3D& p) { is >> p.x >> p.y >> p.z; return is; }
friend std::ostream& operator << (std::ostream& os, const Pos3D& p) { os << p.x << " " << p.y << " " << p.z; return os; }
};
typedef std::vector<Pos3D> Polyhedron;
const Pos3D O3D = { 0, 0, 0 };
const Pos3D MAXP3D = { INF, INF, INF };
std::vector<Pos3D> C3D;//3D
struct Line3D {
Pos3D dir, p0;
Line3D(Pos3D DIR = Pos3D(0, 0, 0), Pos3D P0 = Pos3D(0, 0, 0)) : dir(DIR), p0(P0) {}
};
struct Plane {
ld a, b, c, d;
Plane(ld A = 0, ld B = 0, ld C = 0, ld D = 0) : a(A), b(B), c(C), d(D) {}
Pos3D norm() const { return Pos3D(a, b, c); };
friend std::istream& operator >> (std::istream& is, Plane& f) { is >> f.a >> f.b >> f.c >> f.d; return is; }
friend std::ostream& operator << (std::ostream& os, const Plane& f) { os << f.a << " " << f.b << " " << f.c << " " << f.d << "\n"; return os; }
};
//fn
inline int above(const Plane& S, const Pos3D& p) {
ld ret = p * S.norm() + S.d;
return dcmp(ret);
}
inline Pos3D cross(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) / (d3 - d2); }
inline ld dot(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) * (d3 - d2); }
inline int ccw(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3, const Pos3D& norm) {
Pos3D CCW = cross(d1, d2, d3);
ld ret = CCW * norm;
return zero(ret) ? 0 : ret > 0 ? 1 : -1;
}
inline ld area(const std::vector<Pos3D>& H, const Pos3D& norm) {
ld ret = 0;
if (H.size() < 3) return ret;
Pos3D O = H[0];
int sz = H.size();
for (int i = 0; i < sz; i++) {
Pos3D cur = H[i], nxt = H[(i + 1) % sz];
ret += cross(O, cur, nxt) * norm / norm.mag();
}
return std::abs(ret * .5);
}
inline bool on_seg_strong(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) {
ld ret = dot(d1, d3, d2);
return zero(cross(d1, d2, d3).mag()) && (ret > 0 || zero(ret));
}
inline bool on_seg_weak(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) {
ld ret = dot(d1, d3, d2);
return zero(cross(d1, d2, d3).mag()) && ret > 0;
}
inline Line3D L(const Pos3D& p1, const Pos3D& p2) { return { p2 - p1, p1 }; }
inline Pos3D intersection(const Plane& S, const Line3D& l) {
ld det = S.norm() * l.dir;
if (zero(det)) return { INF, INF, INF };
ld t = -((S.norm() * l.p0 + S.d) / det);
return l.p0 + (l.dir * t);
}
inline Pos3D intersection(const Plane& S, const Pos3D& p1, const Pos3D& p2) {
Line3D l = L(p1, p2);
Pos3D inx = intersection(S, l);
//if (!on_seg_strong(p1, p2, inx)) return { INF, INF, INF };
return inx;
}
inline bool collinear(const Pos3D& a, const Pos3D& b, const Pos3D& c) {
return zero(((b - a) / (c - b)).Euc());
}
inline bool coplanar(const Pos3D& a, const Pos3D& b, const Pos3D& c, const Pos3D& p) {
return zero(cross(a, b, c) * (p - a));
}
inline bool coplanar(const std::vector<Pos3D> H, const Plane& S) {
return zero((cross(H[0], H[1], H[2]) / S.norm()).mag()) * !above(S, H[0]);
}
inline bool above(const Pos3D& a, const Pos3D& b, const Pos3D& c, const Pos3D& p) {// is p strictly above plane
return cross(a, b, c) * (p - a) > 0;
}
inline int prep(std::vector<Pos3D>& p) {//refer to Koosaga'
shuffle(p.begin(), p.end(), std::mt19937(0x14004));
int dim = 1;
for (int i = 1; i < p.size(); i++) {
if (dim == 1) {
if (p[0] != p[i]) std::swap(p[1], p[i]), ++dim;
}
else if (dim == 2) {
if (!collinear(p[0], p[1], p[i]))
std::swap(p[2], p[i]), ++dim;
}
else if (dim == 3) {
if (!coplanar(p[0], p[1], p[2], p[i]))
std::swap(p[3], p[i]), ++dim;
}
}
//assert(dim == 4);
return dim;
}
struct Planar {
Pos3D norm, p0;
//Planar(Pos3D NORM = Pos3D(0, 0, 0), Pos3D P0 = Pos3D(0, 0, 0)) : norm(NORM), p0(P0) {}
Planar(Pos3D a = Pos3D(0, 0, 0), Pos3D b = Pos3D(0, 0, 0), Pos3D c = Pos3D(0, 0, 0)) {
norm = cross(a, b, c).unit();
p0 = a;
}
inline bool coplanar(const Pos3D p) const { return zero(norm * (p - p0)); }
friend std::istream& operator >> (std::istream& is, Planar& P) { is >> P.norm >> P.p0; return is; }
friend std::ostream& operator << (std::ostream& os, const Planar& P) { os << P.norm << " " << P.p0; return os; }
};
struct Face {
int v[3];
Face(int a = 0, int b = 0, int c = 0) { v[0] = a; v[1] = b; v[2] = c; }
inline Pos3D norm(std::vector<Pos3D>& C) const { return cross(C[v[0]], C[v[1]], C[v[2]]); }
Planar P(const Polyhedron& C) const { return Planar(C[v[0]], C[v[1]], C[v[2]]); }
inline ld sph_tri_area(const Polyhedron& C) const {
ld ret = -PI;
Planar s1 = Planar(C[v[0]], C[v[1]], O3D);
Planar s2 = Planar(C[v[1]], C[v[2]], O3D);
Planar s3 = Planar(C[v[2]], C[v[0]], O3D);
ret += PI - atan2((s1.norm / s2.norm).mag(), s1.norm * s2.norm);
ret += PI - atan2((s2.norm / s3.norm).mag(), s2.norm * s3.norm);
ret += PI - atan2((s3.norm / s1.norm).mag(), s3.norm * s1.norm);
return ret;
}
};
std::vector<Face> Hull3D;
struct Edge {
int face_num, edge_num;
Edge(int t = 0, int v = 0) : face_num(t), edge_num(v) {}
};
bool col = 0, cop = 0;
std::vector<Face> convex_hull_3D(std::vector<Pos3D>& candi) {//incremental construction
// 3D Convex Hull in O(n log n)
// Very well tested. Good as long as not all points are coplanar
// In case of collinear faces, returns arbitrary triangulation
// Credit: Benq
// refer to Koosaga'
col = 0, cop = 0;
int suf = prep(candi);
if (suf <= 2) { col = 1; return {}; };
if (suf == 3) { cop = 1; return {}; };
int sz = candi.size();
std::vector<Face> faces;
std::vector<int> active;//whether face is active - face faces outside
std::vector<std::vector<int>> vis(sz);//faces visible from each point
std::vector<std::vector<int>> rvis;//points visible from each face
std::vector<std::array<Edge, 3>> other;//other face adjacent to each edge of face
auto ad = [&](const int& a, const int& b, const int& c) -> void {//add face
faces.push_back(Face(a, b, c));
active.push_back(1);
rvis.emplace_back();
other.emplace_back();
return;
};
auto visible = [&](const int& a, const int& b) -> void {
vis[b].push_back(a);
rvis[a].push_back(b);
return;
};
auto abv = [&](const int& a, const int& b) -> bool {//above
Face tri = faces[a];
return above(candi[tri.v[0]], candi[tri.v[1]], candi[tri.v[2]], candi[b]);
};
auto edge = [&](const Edge& e) -> pi {
return { faces[e.face_num].v[e.edge_num], faces[e.face_num].v[(e.edge_num + 1) % 3] };
};
auto glue = [&](const Edge& a, const Edge& b) -> void {//link two faces by an edge
pi x = edge(a); assert(edge(b) == pi(x.second, x.first));
other[a.face_num][a.edge_num] = b;
other[b.face_num][b.edge_num] = a;
return;
};//ensure face 0 is removed when i = 3
ad(0, 1, 2), ad(0, 2, 1);
if (abv(1, 3)) std::swap(candi[1], candi[2]);
for (int i = 0; i < 3; i++) glue({ 0, i }, { 1, 2 - i });
for (int i = 3; i < sz; i++) visible(abv(1, i), i);//coplanar points go in rvis[0]
std::vector<int> label(sz, -1);
for (int i = 3; i < sz; i++) {//incremental construction
std::vector<int> rem;
for (auto& v : vis[i]) if (active[v]) { active[v] = 0, rem.push_back(v); }
if (!rem.size()) continue;//hull unchanged
int st = -1;//start idx
for (const int& v : rem) {
for (int j = 0; j < 3; j++) {
int o = other[v][j].face_num;
if (active[o]) {//create new face!
int idx1, idx2;
std::tie(idx1, idx2) = edge({ v, j });
ad(idx1, idx2, i);
st = idx1;
int cur = rvis.size() - 1;
label[idx1] = cur;
std::vector<int> tmp;
set_union(rvis[v].begin(), rvis[v].end(), rvis[o].begin(), rvis[o].end(), back_inserter(tmp));
//merge sorted vectors ignoring duplicates
for (auto& x : tmp) if (abv(cur, x)) visible(cur, x);
//if no rounding errors then guaranteed that only x > i matters
glue({ cur, 0 }, other[v][j]);//glue old, new face
}
}
}
for (int x = st, y; ; x = y) {//glue new faces together
int X = label[x];
glue({ X, 1 }, { label[y = faces[X].v[1]], 2 });
if (y == st) break;
}
}
//for (const Face& F : faces) {
// std::cout << F.v[0] << " " << F.v[1] << " " << F.v[2] << " DEBUG\n";
//}
std::vector<Face> hull3D;
for (int i = 0; i < faces.size(); i++) if (active[i]) hull3D.push_back(faces[i]);
return hull3D;
}
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(7);
std::cin >> N;
C3D.resize(N);
Pos3D p;
for (int i = 0; i < N; i++) {
std::cin >> C3D[i];
C3D[i] = C3D[i].unit();
}
C3D.push_back(Pos3D(0, 0, 0));
//int sz1 = C3D.size();
//std::sort(C3D.begin(), C3D.end());
////C3D.erase(unique(C3D.begin(), C3D.end()), C3D.end());
//int sz2 = C3D.size();
//assert(sz1 == sz2);
Hull3D = convex_hull_3D(C3D);
//for (Pos3D& p : C3D) std::cout << p << "\n";
if (col || cop) { std::cout << "1.0000000\n"; return; }
ld suf = 0;
//std::cout << "DEBUG\n";
//std::cout << Hull3D.size() << "\n";
for (const Face& F : Hull3D) {
//std::cout << F.v[0] << " " << F.v[1] << " " << F.v[2] << "\n";
//std::cout << F.P(C3D) << "\n";
//std::cout << F.P(C3D).coplanar(O3D) << "\n";
if (!F.P(C3D).coplanar(O3D)) {
ld a = F.sph_tri_area(C3D);
//std::cout << a << "\n";
suf += a;
}
}
if (suf > 2 * PI) std::cout << "0.0000000\n";
else std::cout << (1 - suf / (4 * PI)) << "\n";
return;
}
int main() { solve(); return 0; }//boj19508 Convex Hull - refer to koosaga, BIGINTEGER
/*
6
1000000 0 0
0 1000000 0
0 0 1000000
-1 0 0
0 -1 0
1000000 1000000 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3948kb
input:
3 1 0 0 0 1 0 0 0 1
output:
0.8750000
result:
ok found '0.8750000', expected '0.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
8 5 -5 -5 -5 5 5 5 5 -5 -5 -5 5 -5 5 -5 5 -5 5 -5 -5 -5 5 5 5
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
3 -1 1 0 1 0 0 -1 -1 0
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 1 0 0 -1 -1 0 -1 1 0
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
50 243766 -981749 -980016 -887005 -856294 -972813 393157 -975105 -847438 -939233 -893701 -913280 -873567 -744684 -879477 175298 -920817 -975741 -439988 -875937 -822164 -408160 -882975 -817414 -680579 -940571 -771153 12852 -941365 -945926 17235 -893328 -840088 -261754 -812552 -901703 207544 -941958 -...
output:
0.9815807
result:
ok found '0.9815807', expected '0.9815807', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
8 812254 195720 -33156 529911 -435521 -383604 -14370 888289 345708 -690806 653853 -726997 -321300 -399682 -545971 555861 336470 833374 -488886 -354891 458819 82311 -890813 432171
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 -145280 790960 -180000 -787200 -229600 0 789440 221920 1800
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
50 999478 -474247 -496198 962208 -411965 -482615 805942 -842420 -961847 886791 -899556 -743082 789762 -941474 -941908 972683 -155427 -719998 794705 -744017 -929021 902297 -863630 -901627 980598 -501847 -535231 923062 -905166 -985843 837866 -895641 -679502 787929 -801321 -974436 920543 -782839 -34119...
output:
0.9758031
result:
ok found '0.9758031', expected '0.9758031', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
50 -964820 -357388 703376 -930203 -671883 928555 -832179 -273067 953284 -983531 568571 938179 -969685 -520593 844012 -970863 -861696 684800 -971051 -59189 934155 -930778 -491257 868715 -953832 -403571 781333 -871268 -642796 940361 -880154 -687233 868394 -949369 -241347 776702 -939248 461851 882467 -...
output:
0.9793125
result:
ok found '0.9793125', expected '0.9793125', error '0.0000000'
Test #10:
score: 0
Accepted
time: 38ms
memory: 10376kb
input:
5000 325248 -133661 -361284 481233 -142552 -110823 518949 -831172 -833803 668725 -422822 697614 -589537 328335 -558764 696832 -294405 -392727 740668 832805 -530710 39539 -200207 638020 887329 -167744 173864 471058 987048 -784500 170570 -397515 250827 215674 92026 975059 919093 42307 303190 -882209 3...
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
3 -340992 961668 0 -961668 -340992 -967841 961668 340992 967841
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4288kb
input:
50 -879543 -759984 873554 -632934 -919219 981992 -475608 -779968 949733 -623896 -997247 845687 -959701 -626703 943891 -450659 -916323 931108 151904 -791579 973882 277355 -752635 983916 -624753 -856722 900274 -675096 -812869 985704 40125 -816928 983587 -588679 -841792 916389 -871984 -532177 991410 -3...
output:
0.9734787
result:
ok found '0.9734787', expected '0.9734787', error '0.0000000'
Test #13:
score: 0
Accepted
time: 37ms
memory: 10268kb
input:
5000 934038 886899 -991824 969256 955964 612570 684004 954442 591390 691816 924278 748910 840228 947266 -319897 964527 834695 709940 894924 997097 -786982 798182 970925 -320286 709305 919199 657838 901952 912287 888545 943446 868751 61853 759830 987188 888382 739172 964813 961309 879483 925654 13731...
output:
0.9643965
result:
ok found '0.9643965', expected '0.9643965', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
50 537773 843738 -813453 473514 932261 -672730 501169 954172 -877312 716608 979825 -723313 778571 968638 -877086 990565 928437 -288953 908547 906751 -457348 939240 886335 -478546 335797 851155 -994631 661426 941015 -821820 741859 952240 -703793 622970 976311 -983443 706414 999464 -625558 443289 9546...
output:
0.9839968
result:
ok found '0.9839968', expected '0.9839968', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4176kb
input:
50 973155 764342 489776 923804 969195 173513 852914 969913 201210 847787 703911 688959 873758 864330 848346 882954 931737 754320 934715 795754 335613 706978 918766 804221 901869 954469 793016 931943 664372 664908 653808 889365 893948 968453 542169 795763 848733 612432 903388 964816 895527 528006 993...
output:
0.9868059
result:
ok found '0.9868059', expected '0.9868059', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
50 682834 819655 -866429 973155 -700941 -962027 871625 706120 -873259 926776 21695 -991263 844652 218052 -920955 869541 -427092 -990805 957902 510181 -907259 539519 951146 -945063 892985 468197 -823181 765442 274806 -937573 739015 364391 -962514 668988 810454 -983500 900315 48147 -906753 914094 -301...
output:
0.9795337
result:
ok found '0.9795337', expected '0.9795337', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
50 -950608 985546 522648 -426708 905003 818017 -935417 694620 614168 -843600 633453 874179 -459334 997508 739162 -201009 920460 984356 -633781 977241 701010 -870910 952109 218776 -898955 957441 284022 -763632 848743 861562 -681306 770061 798761 -554050 877027 869985 -894621 853518 615207 -945291 954...
output:
0.9825206
result:
ok found '0.9825206', expected '0.9825206', error '0.0000000'
Test #18:
score: 0
Accepted
time: 37ms
memory: 10316kb
input:
5000 695401 -945257 -591056 694067 -977684 -267594 988084 -992121 -850813 742331 -856058 -751953 913710 -907387 -208739 996804 -949905 -432558 924136 -771126 -440786 816251 -956324 -167953 719674 -949801 -348348 910181 -953167 17153 831401 -973771 -318180 935224 -713815 -804175 884779 -789263 -80188...
output:
0.9711829
result:
ok found '0.9711829', expected '0.9711829', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
50 819360 -911392 -991868 985245 -835524 906250 863918 -995497 301168 935090 -910997 200986 995426 -771507 -762578 963266 -776763 -954949 880688 -876559 -571338 989465 -943975 -169758 999021 -747786 172884 841150 -904894 -182889 946528 -827744 -87093 938799 -967289 -40979 989363 -825805 716609 96159...
output:
0.9768602
result:
ok found '0.9768602', expected '0.9768602', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
50 -905056 991526 -854786 -821830 775926 -975100 -907922 -335144 -979903 -971065 -265056 -993626 -825717 693541 -961819 -971925 629486 -802341 -970545 -652051 -926125 -812832 630087 -925382 -918053 720984 -826095 -724335 984291 -984338 -801623 815002 -960139 -829353 336818 -998901 -834393 898069 -91...
output:
0.9839439
result:
ok found '0.9839439', expected '0.9839439', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
50 711196 877304 494401 928717 997767 -246038 817158 943532 698927 513607 993041 219753 994648 946728 -549694 781912 940341 882911 890955 949934 949447 630752 989455 -77744 811869 915482 314450 808175 936445 735747 770758 975874 900764 913564 896580 43237 896088 976640 697780 831970 982390 884813 95...
output:
0.9724992
result:
ok found '0.9724992', expected '0.9724992', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4192kb
input:
3 0 10000 1 -10000 -10 1 10000 -10 1
output:
0.5158946
result:
ok found '0.5158946', expected '0.5158946', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4292kb
input:
50 657445 -982225 761943 624620 -878166 682726 549277 -747617 995595 445418 -791825 854936 8593 -902503 925236 524749 -918734 808226 934402 -600773 907736 868306 -700860 905493 539588 -840913 932940 864372 -843700 740935 193564 -898660 912851 13826 -939410 887156 997974 -841848 757288 683480 -809703...
output:
0.9869132
result:
ok found '0.9869132', expected '0.9869132', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
4 0 -750012 631822 0 750012 -631822 648305 -631822 -750012 -648305 631822 750012
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 38ms
memory: 10428kb
input:
5000 -999661 -130158 835188 -685077 -832767 986977 -992925 -679996 950267 -891416 -763210 906159 -991301 233255 975525 -892886 -770204 900901 -896956 -253790 972148 -861669 -726033 900858 -843905 832983 970899 -892538 -541729 868729 -799189 -675767 942192 -881936 -281787 961527 -900639 -352890 83186...
output:
0.9692486
result:
ok found '0.9692486', expected '0.9692486', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
50 43674 79360 -408 12890 21640 -408 24730 43840 -408 -51046 -98240 -408 36570 66040 -408 -58150 -111560 -408 -55782 -107120 -408 -15526 -31640 -408 -24998 -49400 -408 -48678 -93800 -408 5786 8320 -408 55514 101560 -408 38938 70480 -408 -27366 -53840 -408 -8422 -18320 -408 -41574 -80480 -408 29466 5...
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #27:
score: 0
Accepted
time: 38ms
memory: 10132kb
input:
5000 482833 -866437 -498378 410075 -21441 331129 -576234 233055 734457 -205727 -154148 -460577 -336266 340103 -892982 -853071 32201 -626147 462510 54262 -64659 658538 -183950 -882647 -381194 -201649 -527918 -268634 711752 -111826 -510396 985255 -190041 -850331 899608 -454317 -640269 552472 111593 -8...
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
50 797216 884820 759341 925615 489184 993201 925036 782549 955421 829586 819769 776200 883159 916720 835808 860406 925937 842804 770572 966647 938747 619534 940295 845040 650721 878227 795267 817979 966314 669729 998393 864265 795411 928879 623858 929742 681619 949196 679127 947698 687146 883357 711...
output:
0.9817713
result:
ok found '0.9817713', expected '0.9817713', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
8 68354 -743608 75085 930413 -748845 -429976 172471 465691 63689 205005 715069 -188694 -718629 -729238 670445 -821402 877418 -272660 -389232 -347507 -837140 -822614 657026 817624
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #30:
score: 0
Accepted
time: 1ms
memory: 4272kb
input:
50 576411 -914687 -927830 421638 -949904 -952816 951839 -964998 -509189 707888 -659125 -850311 431466 -908347 -887774 887469 -879067 -681728 896352 -894237 -853988 617437 -846677 -784935 918776 -793701 -704619 781906 -894737 -673198 799636 -920934 -968713 250708 -999610 -971097 950782 -785524 -95214...
output:
0.9864993
result:
ok found '0.9864993', expected '0.9864993', error '0.0000000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
4 0 115015 212952 -268579 212952 -115015 268579 -212952 115015 0 -115015 -212952
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
50 -998058 -728188 257103 -975706 -541876 794206 -955529 -436910 716246 -975856 866727 776333 -973722 -152058 958441 -978724 676106 955621 -965979 -483557 739016 -994119 809262 967474 -971232 406582 554150 -961195 399767 763328 -995612 -680431 652244 -968813 -902905 464861 -965242 -214184 984986 -97...
output:
0.9440720
result:
ok found '0.9440720', expected '0.9440720', error '0.0000000'
Test #33:
score: 0
Accepted
time: 1ms
memory: 4204kb
input:
50 -956843 -523681 -660824 -922452 47064 -988471 -539189 -900713 -976781 -814379 -538015 -914455 -937267 -548243 -889819 -964656 -940507 -547751 -881791 -871331 -918631 -855258 -762652 -705856 -749031 -711011 -939880 -853433 -755362 -725200 -718869 -602608 -997693 -615102 -593600 -981427 -964499 -56...
output:
0.9772762
result:
ok found '0.9772762', expected '0.9772762', error '0.0000000'
Test #34:
score: 0
Accepted
time: 38ms
memory: 10308kb
input:
5000 771417 550388 356379 994145 269481 -164580 -827669 508749 -675326 -633191 461827 112287 722242 -387924 717600 832714 840221 796351 636729 -693716 799441 -232982 345849 116049 -871284 458319 737030 -893638 667580 -403886 -650333 -685033 809571 -707271 105170 -736574 -775264 -150549 -599071 -6242...
output:
0.0000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #35:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
50 -718005 -667009 -851344 -981123 -622533 -666108 -808883 -930473 -795601 -587648 -827065 -973258 -924290 -707924 -908553 -926946 -808541 -969790 -940303 -719702 -962827 -734173 -730887 -831569 -803767 -950852 -757312 -790005 -994073 -953096 -843310 -739313 -881799 -917548 -962532 -881703 -744026 -...
output:
0.9855624
result:
ok found '0.9855624', expected '0.9855624', error '0.0000000'
Test #36:
score: 0
Accepted
time: 1ms
memory: 4264kb
input:
50 -791021 -903563 460193 -960184 -892205 32485 -991566 -614653 847898 -676001 -947377 644421 -553702 -977811 778687 -858372 -647965 969536 -779247 -976283 526674 -816875 -854563 942343 -616497 -856599 954775 -985085 -931059 814974 -834744 -814565 963047 -652416 -987418 501260 -817533 -795274 623031...
output:
0.9806589
result:
ok found '0.9806589', expected '0.9806589', error '0.0000000'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 -478656 -144608 1400 480000 140000 0 -182400 446800 -140000
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #38:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
50 878932 695177 -744907 795392 607992 -895739 843038 676432 -757107 844074 713601 -849818 780410 667962 -797736 880677 971120 -511771 746801 481040 -999336 757697 960108 -760723 748535 829252 -830692 756291 571961 -862424 875781 485501 -860691 832945 778789 -700807 972507 632207 -997589 405910 8597...
output:
0.9841908
result:
ok found '0.9841908', expected '0.9841908', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
50 -22570 -18240 1000 28470 20040 1000 5270 2640 1000 111990 82680 1000 107350 79200 1000 102710 75720 1000 84150 61800 1000 70230 51360 1000 -82890 -63480 1000 -106090 -80880 1000 -73610 -56520 1000 -45770 -35640 1000 47030 33960 1000 -110730 -84360 1000 42390 30480 1000 116630 86160 1000 98070 722...
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #40:
score: 0
Accepted
time: 1ms
memory: 4292kb
input:
50 -977059 127392 -925327 -915623 466955 -730820 -880430 405599 -890305 -928716 447918 -961086 -991439 -257253 -862206 -983149 -849441 -885573 -964735 -908171 -761625 -899553 446919 -834309 -919014 931751 -885764 -974955 556656 -967294 -975289 -26061 -908522 -979983 -522974 -744729 -935981 932862 -8...
output:
0.9780374
result:
ok found '0.9780374', expected '0.9780374', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 4184kb
input:
3 0 100000 1 100000 -100 1 -100000 -100 1
output:
0.5015947
result:
ok found '0.5015947', expected '0.5015947', error '0.0000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 4252kb
input:
50 903978 -375821 872746 935925 -231160 920014 724683 -745695 916431 694975 -909655 920268 939944 704842 949723 883615 117874 976749 996053 -152654 693693 966413 -993866 898094 839102 96818 976882 902275 -156053 782295 741589 -957561 982813 982246 573939 953720 732081 -982040 883335 966966 -694982 9...
output:
0.9690449
result:
ok found '0.9690449', expected '0.9690449', error '0.0000000'
Test #43:
score: 0
Accepted
time: 1ms
memory: 4256kb
input:
50 980872 782844 476990 930453 926106 732235 766523 939649 596622 875585 926413 561527 969024 624900 705621 897221 616746 874981 930606 862874 957054 993864 622033 812743 872866 788284 374927 571741 906390 913193 799357 833531 993992 963931 766224 973882 960445 899636 63461 861777 772638 977949 7605...
output:
0.9837061
result:
ok found '0.9837061', expected '0.9837061', error '0.0000000'
Test #44:
score: -100
Runtime Error
input:
5000 -71751 37393 -21760 -1423 35289 -7225 5949 -133582 10370 -79771 60378 -25585 -16499 115432 -17935 -145099 -55268 -27880 -29655 79265 -17170 -42367 -76369 -4930 -36267 16956 -12580 -120843 -43526 -24055 -47367 41381 -17170 7177 69739 -8755 -14767 103081 -16405 8713 -23309 425 31937 -134191 15725...