QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731869#4854. Viruscrimson231AC ✓4ms4456kbC++2315.2kb2024-11-10 12:02:292024-11-10 12:02:31

Judging History

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

  • [2024-11-10 12:02:31]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:4456kb
  • [2024-11-10 12:02:29]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
typedef long long ll;
typedef long double ld;
//typedef double ld;
typedef std::pair<int, int> pi;
typedef std::vector<int> Vint;
typedef std::vector<ld> Vld;
const ld INF = 1e17;
const ld TOL = 1e-10;
const ld EPS = 1e-6;
const ld PI = acos(-1);
const int LEN = 1e3;
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
inline ll sq(int x) { return (ll)x * x; }
inline ld norm(ld th) {
	while (th < 0) th += 2 * PI;
	while (sign(th - 2 * PI) >= 0) th -= 2 * PI;
	return th;
}
int gcd(int a, int b) { while (b) { int tmp = a % b; a = b; b = tmp; } return a; }
int gcd(int a, int b, int c) { int x = gcd(a, b); return gcd(x, c); }
int gcd(int a, int b, int c, int d) { a = std::abs(a); b = std::abs(b); c = std::abs(c); d = std::abs(d); int x = gcd(a, b, c); return gcd(x, c); }

int N, M, T, Q;
ld sc[4];
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; }
	bool operator <= (const Pos& p) const { return *this < p || *this == p; }
	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 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 ld& scale) { x *= scale; y *= scale; return *this; }
	Pos& operator /= (const ld& 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 }; }
	ld xy() const { return x * y; }
	Pos rot(ld the) { return { x * cos(the) - y * sin(the), x * sin(the) + y * cos(the) }; }
	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); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	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; }
	bool close(const Pos& p) const { return zero((*this - p).Euc()); }
	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> Polygon;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
ld cross(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) { return sign(cross(d1, d2, d3)); }
ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
ld dot(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3); }
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && sign(dot(d1, d3, d2)) >= 0; }
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && sign(dot(d1, d3, d2)) > 0; }
ld area(const Polygon& H) {
	ld ret = 0;
	int sz = H.size();
	for (int i = 0; i < sz; i++) ret += H[i] / H[(i + 1) % sz];
	return ret * .5;
}
struct Linear {//ps[0] -> ps[1]
	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());
	}
};
typedef std::vector<Linear> Planes;
ld dist(const Pos& d1, const Pos& d2, const Pos& t) { return cross(d1, d2, t) / (d1 - d2).mag(); }
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 projection(const Pos& s1, const Pos& s2, const Pos& p) { return intersection(s1, s2, p, p + ~(s2 - s1)); }
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) {
	auto check = [&](Linear& u, Linear& v, Linear& w) -> bool {
		return w.include(intersection(u, v));
		};
	std::sort(HP.begin(), 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;
}
Planes make_hp(const Polygon& H) {
	Planes V;
	int sz = H.size();
	for (int i = 0; i < sz; i++) V.push_back(Linear(H[i], H[(i + 1) % sz]));
	return V;
}
Pos centroid(const Polygon& H) {
	Pos cen = Pos(0, 0);
	ld A = 0;
	int sz = H.size();
	for (int i = 0; i < sz; i++) {
		ld a = H[i] / H[(i + 1) % sz];
		cen += (H[i] + H[(i + 1) % sz]) * a;
		A += a;
	}
	A *= .5;
	cen /= 6;
	if (!zero(A)) cen /= A;
	return cen;
}
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; }
	ld operator * (const Pos3D& p) const { return x * p.x + y * p.y + z * p.z; }
	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;
	}
	Pos3D operator + (const Pos3D& p) const { return { x + p.x, y + p.y, z + p.z }; }
	Pos3D operator - (const Pos3D& p) const { return { x - p.x, y - p.y, z - p.z }; }
	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& n) const { return { x * n, y * n, z * n }; }
	Pos3D operator / (const ld& n) const { return { x / n, y / n, z / n }; }
	Pos3D& operator *= (const ld& n) { x *= n; y *= n; z *= n; return *this; }
	ld Euc() const { return x * x + y * y + z * z; }
	ld mag() const { return sqrtl(Euc()); }
	Pos3D unit() const { return *this / mag(); }
	Pos3D norm(const Pos3D& p) const { return (*this / p).unit(); }
	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; }

};
const Pos3D O3D = { 0, 0, 0 };
const Pos3D X_axis = { 1, 0, 0 };
const Pos3D Y_axis = { 0, 1, 0 };
const Pos3D Z_axis = { 0, 0, 1 };
const Pos3D INVAL3D = { INF, INF, INF };
typedef std::vector<Pos3D> Polygon3D;
typedef std::vector<Polygon3D> Polyhedron;
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) {}
	Plane& operator *= (const ld& s) { a *= s; b *= s; c *= s; d *= s; return *this; }
	Pos3D norm() const { return Pos3D(a, b, c); };
	Plane operator + (const ld& n) const { return { a, b, c, d + n }; }
	Plane operator - (const ld& n) const { return { a, b, c, d - n }; }
	Plane& operator += (const ld& n) { d += n; return *this; }
	Plane& operator -= (const ld& n) { d -= n; return *this; }
	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; return os; }
} knife;
typedef std::vector<Plane> Surfaces;
int above(const Plane& S, const Pos3D& p) { return sign(p * S.norm() + S.d); }
void update_sc(const Plane& p) {
	ld angle1 = -atan2(p.b, p.a);
	ld dx = sqrtl(p.a * p.a + p.b * p.b);
	ld angle2 = -atan2(dx, p.c);
	sc[0] = sin(angle1);
	sc[1] = cos(angle1);
	sc[2] = sin(angle2);
	sc[3] = cos(angle2);
	return;
}
Pos3D rotate(const Pos3D& p) {
	ld x = p.x * sc[1] - p.y * sc[0], y = p.x * sc[0] + p.y * sc[1], z = p.z;
	return Pos3D(z * sc[2] + x * sc[3], y, z * sc[3] - x * sc[2]);
}
Pos convert(Pos3D p, const Pos3D& v) {
	p -= v;
	p = rotate(p);
	return Pos(p.x, p.y);
}
Pos3D recover(const Pos& p2D, const Pos3D& v) {
	ld x = p2D.x * -sc[3];
	ld y = p2D.y;
	ld z = p2D.x * sc[2];
	Pos3D p = Pos3D(x * -sc[1] + y * sc[0], x * sc[0] + y * sc[1], z);
	return p + v;
}
typedef std::vector<Pos3D> Polygon3D;
typedef std::vector<Polygon3D> Polyhedron;
Pos3D cross(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) / (d3 - d2); }
ld dot(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return (d2 - d1) * (d3 - d2); }
int ccw(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3, const Pos3D& norm) { return sign(cross(d1, d2, d3) * norm); }
bool on_seg_strong(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return zero(cross(d1, d2, d3).mag()) && sign(dot(d1, d3, d2)) >= 0; }
bool on_seg_weak(const Pos3D& d1, const Pos3D& d2, const Pos3D& d3) { return zero(cross(d1, d2, d3).mag()) && sign(dot(d1, d3, d2)) > 0; }
Line3D L(const Pos3D& p1, const Pos3D& p2) { return { p2 - p1, p1 }; }
ld dist(const Plane& s, const Pos3D& p) { return (s.norm() * p + s.d) / s.norm().mag(); }
Pos3D offset(const Plane& s, const Pos3D& p) { ld d = dist(s, p); return s.norm().unit() * -d; }
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);
}
Pos3D intersection(const Plane& S, const Pos3D& p1, const Pos3D& p2, const bool& f = 0) {
	Line3D l = L(p1, p2);
	Pos3D inx = intersection(S, l);
	if (f && !on_seg_strong(p1, p2, inx)) return { INF, INF, INF };
	return inx;
}
int intersection(const Plane& p1, const Plane& p2, Line3D& l) {
	Pos3D n1 = p1.norm();
	Pos3D n2 = p2.norm();
	Pos3D dir = n2 / n1;
	dir = dir.unit();
	if (zero(dir.mag())) {
		ld f = n1 * n2;
		ld d1 = dist(p1, O3D);
		ld d2 = dist(p2, O3D);
		if (sign(f) > 0) return sign(d2 - d1) >= 0 ? 0 : -1;
		else return sign(d2 + d1) >= 0 ? 0 : -2;
	}
	Pos3D q1 = intersection(p1, Line3D(n1, O3D));
	Pos3D v1 = n1 / dir;
	Pos3D p0 = intersection(p2, Line3D(v1, q1));
	l = Line3D(dir, p0);
	return 1;
}
int A_[LEN], B_[LEN], C_[LEN], D_[LEN];
bool V[LEN];
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;
	Surfaces S(N);
	int ii = 0;
	for (Plane& p : S) {
		int a, b, c, d;
		std::cin >> a >> b >> c >> d;
		A_[ii] = a; B_[ii] = b; C_[ii] = c; D_[ii] = d;
		int x = gcd(a, b, c, d);
		a /= x; b /= x; c /= x; d /= x;
		ii++;
		a *= -1; b *= -1; c *= -1;
		p = Plane(a, b, c, d);
		p += EPS;
	}
	ld bnd = 1e7;
	Pos p1 = Pos(-bnd, -bnd),
		p2 = Pos(bnd, -bnd),
		p3 = Pos(bnd, bnd),
		p4 = Pos(-bnd, bnd);
	Planes B = {
		Linear(p1, p2),
		Linear(p2, p3),
		Linear(p3, p4),
		Linear(p4, p1)
	};
	Pos3D q;
	bool f0 = 0;
	for (int i = 0; i < N; i++) {
		update_sc(S[i]);
		Pos3D v = offset(S[i], O3D);
		Line3D l;
		int f = 1;
		Planes hp = B;
		memset(V, 0, sizeof V);
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			f = intersection(S[i], S[j], l);
			if (f == -2) { std::cout << "banana\n"; return; }
			if (f == -1) break;
			if (f == 0) continue;
			Pos s = convert(l.p0, v);
			Pos e = convert(l.p0 + l.dir, v);
			hp.push_back(Linear(s, e));
			V[j] = 1;
		}
		if (f == -1) continue;
		Polygon hpi = half_plane_intersection(hp);
		if (!hpi.size()) continue;
		int k = 0;
		for (int j = 0; j < N; j++) {
			if (i == j || !V[j]) continue;
			if (!k) {
				f = intersection(S[i], S[j], l);
				k = 1;
				//std::cout << "fffffff::" << f << "\n";
				break;
			}
			else if (k) {
				ld ff = S[j].norm() * l.dir;
				if (zero(ff)) continue;
				Pos3D inx = intersection(S[j], l);
				Pos3D v = l.p0 - inx;
				if (ff > 0 && v * l.dir > 0) l.p0 = inx;
				else if (ff < 0 && v * l.dir < 0) l.p0 = inx;
			}
		}
		Pos cen = centroid(hpi);
		q = recover(cen, v);
		l = { S[i].norm(), q };
		q = intersection(S[i], l);
		q = recover(hpi[0], v);
		//q = l.p0;
		f0 = 1;
		for (int i = 0; i < ii; i++) {
			ld dd = (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001);
			//std::cout << D_[i] - dd << "\n";
			if (D_[i] < dd) { f0 = 0; break; }
		}
		if (!f0) continue;
		break;
		//return;
	}
	if (f0) {
		//q *= -1;
		//q = Pos3D(3.0, 5.0, 2.0);
		//for (const Plane& p : S) {
			//std::cout << "dist:: " << dist(p, q) << "\n";
			//std::cout << "p:: " << p << "\n";
			//std::cout << "p * q:: " << p.norm() * q << "\n";
			//std::cout << "-p * q:: " << p.norm() * -1 * q << "\n";
			//std::cout << (p.a * q.x + p.b * q.y + p.c * q.z - 0.001 <= p.d) << "\n";
			//std::cout << (-p.a * q.x - p.b * q.y - p.c * q.z - 0.001 <= p.d) << "\n";
			//std::cout << (-p.a * q.x - p.b * q.y - p.c * q.z - 0.001) << " " << (p.d) << "\n";
			//std::cout << (p.norm() * -1 * q - 0.001) << " " << (p.d) << "\n";
			//std::cout << -(p.a * q.x + p.b * q.y + p.c * q.z) << "\n";
			//std::cout << p.norm() * -1 * q << "\n";
		//}
		for (int i = 0; i < ii; i++) {
			//std::cout << D_[i] - (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << "\n";
			ld dd = (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001);
			//assert(D_[i] >= dd);
			//std::cout << D_[i] - dd << "\n";
		}
		std::cout << q << "\n";
	}
	else std::cout << "banana\n";
	return;
}
int main() { solve(); return 0; }//boj14118

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4360kb

input:

10
344 -792 -688 515
-271 653 -152 715
-320 -275 -324 -283
-182 142 -387 -584
75 406 -424 868
-139 -647 54 150
-981 -401 -734 -202
-858 555 -884 954
-94 891 -557 457
-216 -281 -743 -916

output:

11470968.795842858920878 -1811641.434340501394331 7820977.863034321423129

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 4384kb

input:

100
733 991 -342 -694
328 446 -154 -351
-631 -850 290 334
694 942 -326 540
439 599 -207 -299
-552 -729 249 -667
728 984 -343 -920
341 459 -159 955
-342 -455 154 -307
-595 -793 269 834
687 944 -326 -420
-688 -911 310 866
538 740 -257 -928
708 964 -337 358
574 789 -273 44
490 670 -235 -408
-387 -518 1...

output:

-188673.743597087254983 3464986.538361090593753 9635978.068594082464188

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 4296kb

input:

100
-153 53 -16 -823
-232 185 -29 -929
120 -120 13 811
-268 268 -36 -963
76 -79 9 536
-218 206 -22 -705
-136 117 -16 -439
-316 300 -36 -978
-287 308 -36 -857
-207 250 -28 -591
-318 253 -33 -959
-301 353 -42 -857
-201 153 -21 -599
-310 393 -37 -813
-334 224 -36 -994
-313 323 -37 -835
-289 338 -41 -75...

output:

10.036029713996444 11.175749767691926 72.905108264881477

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 4444kb

input:

99
-384 -136 880 952
-367 -107 887 749
-332 -44 908 308
-285 -28 799 196
-266 -127 544 889
-266 -101 596 707
-265 -88 619 616
-253 -6 747 42
-249 -135 477 945
-244 -14 704 98
-242 -25 676 175
-239 -14 689 98
-236 -97 514 679
-198 -88 418 616
-190 56 682 -392
-188 111 786 -777
-184 130 812 -910
-178 ...

output:

-10870528.691735740462718 7247012.127823827685461 -3623509.563911912554431

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 4380kb

input:

100
-187 -49 -380 -466
41 108 809 -429
-243 -122 -929 -286
-91 52 381 -639
94 -111 -821 981
349 113 870 759
-109 81 596 -864
35 -112 -833 758
-94 -71 -537 25
5 49 366 -243
-157 -41 -318 -387
-20 25 185 -212
306 79 613 782
-176 -92 -700 -173
191 -21 -142 869
194 76 582 359
-128 56 408 -798
-259 -102 ...

output:

106865.912407004914435 10365607.503480347959339 -1389205.861291178822853

result:

ok correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 4360kb

input:

100
786 -1 179 -696
766 -1 87 808
818 -1 109 590
982 -1 133 674
942 -1 186 -347
911 -1 113 801
676 -1 140 -363
907 -1 175 -265
820 -1 180 -611
957 -1 195 -455
890 -1 193 -622
678 -1 144 -425
815 -1 115 479
945 -1 174 -134
889 -1 193 -625
915 -1 175 -241
784 -1 85 896
690 -1 133 -202
984 -1 196 -391
...

output:

5397.464560322134902 9999999.678697256546002 23920.936486432014714

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 4364kb

input:

4
10 4 -7 13
-10 -4 7 -13
5 3 4 14
-5 -3 -4 -14

output:

4437665.319910516267100 -8995263.486304801774168 1199369.464840706329937

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 4356kb

input:

6
5 9 1 1000
-5 -9 -1 -1000
4 2 1 197
-4 -2 -1 -197
17 53 -12 4
-17 -53 12 -4

output:

-119.722222018518524 131.817460288359759 412.253968497354487

result:

ok correct

Test #9:

score: 0
Accepted
time: 4ms
memory: 4136kb

input:

100
-952 -626 278 737
950 778 366 473
-65 -427 -979 429
212 -804 -495 797
161 904 718 334
469 577 261 991
413 215 65 -216
23 -388 -818 909
483 -529 234 -626
-59 195 386 963
266 -9 963 620
58 110 837 -300
-37 -520 136 -708
74 -633 -927 378
687 670 877 -370
169 -402 940 389
290 -993 831 458
-562 305 4...

output:

banana

result:

ok no sol

Test #10:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

100
271 337 62 -62
-451 877 289 -942
127 643 203 118
-511 -715 -209 -670
889 -435 -336 -514
-747 900 420 -54
654 665 80 -392
-831 85 179 146
-231 -41 -32 -682
189 727 243 386
-173 323 81 -666
-134 -711 -266 -616
409 -27 -41 434
133 -227 -108 -122
-31 27 87 874
269 -443 -111 978
74 34 -33 -384
-472 3...

output:

1.999999998099192 -3.999999998106140 11.999999993383749

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

1
0 0 -1 4

output:

-10000000.000000000000000 10000000.000000000000000 -4.000001000000000

result:

ok correct

Test #12:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

100
-725 -90 721 177
546 728 652 -986
-704 280 913 -405
-690 -400 836 -102
-126 434 968 241
-374 406 818 -667
-441 40 656 -750
-692 952 796 -615
590 937 289 179
-878 -8 745 56
-355 297 285 967
-264 -169 643 355
455 932 110 470
-369 941 873 -765
5 542 594 662
-739 699 300 -143
-875 375 214 -813
0 169...

output:

-0.362256243601686 2.694911887161725 -17.062102609054174

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 4360kb

input:

2
1 -1 0 997
999 -1000 0 -1000

output:

998000.000998718992832 997003.000997717970279 10000000.000000000000000

result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

1
0 0 -1 -4

output:

-10000000.000000000000000 10000000.000000000000000 3.999999000000000

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 4252kb

input:

2
0 -1 0 -4
0 -20 0 -80

output:

-10000000.000000000000000 3.999999000000000 10000000.000000000000000

result:

ok correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 4228kb

input:

1
1 0 0 -1000

output:

-999.999999000612323 -10000000.000000000000000 10000000.000000000000000

result:

ok correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 4328kb

input:

5
1 1 0 4
-1 -1 0 -4
1 0 0 2
0 1 0 2
0 5 0 10

output:

2.000001000432978 2.000000000432978 10000000.000000000000000

result:

ok correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 4368kb

input:

4
0 1 1 4
0 -1 -1 -4
0 0 1 2
0 1 0 2

output:

10000000.000000000000000 2.000000000306439 2.000001000305885

result:

ok correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 4236kb

input:

5
1 0 1 4
-1 0 -1 -4
1 0 0 2
0 0 1 2
1 0 1 4

output:

1.999999999387663 -10000000.000000000000000 2.000000999387690

result:

ok correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 4332kb

input:

4
-367 -389 983 596
-984 737 -73 290
841 -167 -642 129
-1 0 0 -300

output:

5092245.013289397488279 7272231.880775780695330 4778995.643437422664192

result:

ok correct

Test #21:

score: 0
Accepted
time: 1ms
memory: 4400kb

input:

100
520 -928 907 702
-366 125 -26 168
-921 -645 -942 -395
446 -400 885 -797
-20 -927 957 -501
-443 147 587 -957
-556 -973 -57 -266
342 -119 723 -375
721 -913 73 -440
-195 -978 -687 499
-261 -473 594 125
-732 -155 651 -421
-793 314 611 -306
-837 -561 -665 435
426 -448 498 -512
-95 -984 599 684
-530 3...

output:

7168139.392430460773994 7403787.669845698047993 -4330389.275234842303689

result:

ok correct

Test #22:

score: 0
Accepted
time: 1ms
memory: 4288kb

input:

100
-527 -28 87 953
-198 3 166 977
-102 -11 65 865
10 68 38 978
-322 19 19 780
-175 82 27 916
-96 -28 160 429
-919 145 36 997
-116 7 40 492
-96 -26 183 653
-364 1 254 993
81 32 -10 609
-520 33 138 913
-72 -40 135 846
-10 -13 -74 805
-472 26 68 983
-91 24 139 848
-564 -1 39 665
-490 -8 156 830
-161 -...

output:

-1.269481562380136 -22.769039323620930 -4.063791763628939

result:

ok correct

Test #23:

score: 0
Accepted
time: 1ms
memory: 4332kb

input:

100
298 523 -774 -722
-542 957 -89 752
-30 452 -387 -459
549 248 -664 -891
-513 964 -353 654
-338 806 -346 275
155 769 -669 873
167 986 -765 -199
-342 739 -238 996
-894 400 555 534
-23 308 -245 21
117 804 -767 -690
515 137 -586 -617
361 823 -834 508
155 660 -779 -929
423 713 -866 234
-255 758 -422 -...

output:

8331206.758432535763859 5581689.853494264998972 9282723.311500855647864

result:

ok correct

Test #24:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

100
865 593 473 -26
-885 -74 71 -992
328 78 212 -6
467 -430 558 855
-223 230 329 -425
-374 173 898 -197
-867 251 -134 -521
-168 -177 -107 488
-322 539 -190 42
-862 641 87 767
816 -398 501 54
-635 -693 157 -405
720 157 635 906
231 787 994 698
126 803 842 -431
-108 402 938 -933
705 -454 800 138
286 -4...

output:

2.646979061563579 -1.405716088738574 -6.391408744261249

result:

ok correct

Test #25:

score: 0
Accepted
time: 2ms
memory: 4456kb

input:

98
226 939 41 162
-887 277 920 -480
-112 -272 -769 -235
-672 -596 731 -385
-901 660 667 459
-528 149 693 -576
-962 -614 919 -824
-357 -217 -131 596
-606 920 244 769
-665 -371 838 223
-902 -741 -784 946
13 258 -778 -615
-531 -307 284 -292
-977 633 7 -20
-594 823 565 962
-885 -908 206 -898
283 752 185...

output:

8723252.947215776982375 -5172891.663235449630065 3801617.187743741803843

result:

ok correct

Test #26:

score: 0
Accepted
time: 0ms
memory: 4316kb

input:

100
6 66 -801 292
-45 -547 -223 115
-40 -487 -732 -578
1 13 -333 -813
-75 -903 -869 -951
-63 -738 923 -226
-46 -542 451 -670
47 584 366 47
71 879 74 -370
-70 -836 -563 65
-69 -822 -601 -380
64 791 -683 689
73 916 544 -103
57 719 533 -210
-39 -447 676 286
58 720 -389 986
48 599 -403 -202
-43 -499 502...

output:

9967845.352486609403059 -807311.294519905015193 8145.113204248310367

result:

ok correct

Test #27:

score: 0
Accepted
time: 0ms
memory: 4364kb

input:

100
-27 779 394 -368
-17 -705 -398 -545
22 -940 -486 -213
-917 346 -730 -919
351 37 371 835
-100 272 47 582
733 -866 265 12
220 618 554 -3
-996 185 -896 503
699 -557 398 -859
122 -631 -219 775
-241 -792 -669 -77
-558 692 -184 -227
187 -594 -134 -594
857 61 890 -765
592 -755 184 728
-200 692 174 762
...

output:

203976.932675205654405 110233.746712260622381 -203972.283011724631280

result:

ok correct

Extra Test:

score: 0
Extra Test Passed