QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408413#5046. Mooncrimson231RE 38ms10428kbC++1711.9kb2024-05-10 10:46:352024-05-10 10:46:37

Judging History

你现在查看的是最新测评结果

  • [2024-05-10 10:46:37]
  • 评测
  • 测评结果:RE
  • 用时:38ms
  • 内存:10428kb
  • [2024-05-10 10:46:35]
  • 提交

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...

output:


result: