QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #731811 | #4854. Virus | crimson231 | WA | 4ms | 4420kb | C++23 | 35.3kb | 2024-11-10 11:29:12 | 2024-11-10 11:29:13 |
Judging History
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); }
//ld randTOL() {
// ld rand01 = rand() / (ld)RAND_MAX;
// ld err = (rand01 - .5) * TOL;
// return err;
//}
//Pos3D add_noise(const Pos3D& p) {
// ld rand01 = rand() / (ld)RAND_MAX;
// ld err = (rand01 - .5) * TOL;
// return p + Pos3D(randTOL(), randTOL(), randTOL());
//}
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) {
//std::cout << "pppp1:: " << p << "\n";
//std::cout << "vvvv1:: " << v << "\n";
p -= v;
//std::cout << "pppp2:: " << p << "\n";
p = rotate(p);
//std::cout << "pppp3:: " << p << "\n";
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];
//std::cout << "recover:: sc[2]:: " << sc[2] << "\n";
//std::cout << "recover:: sc[3]:: " << sc[3] << "\n";
//std::cout << "recover:: x:: " << x << "\n";
//std::cout << "recover:: y:: " << y << "\n";
//std::cout << "recover:: z:: " << z << "\n";
Pos3D p = Pos3D(x * -sc[1] + y * sc[0], x * sc[0] + y * sc[1], z);
//std::cout << "recover:: p:: " << p << "\n";
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);
//std::cout << "intersection::\n";
//std::cout << "t:: " << t << "\n";
//std::cout << "S:: " << S << "\n";
//std::cout << "l:: dir:: " << l.dir << " p0:: " << l.p0 << "\n";
//std::cout << "inx:: " << l.p0 + (l.dir * t) << "\n";
//std::cout << "intersection::\n";
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 A_[LEN], B_[LEN], C_[LEN], D_[LEN];
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);
//ld d1 = p1.d;
//ld d2 = p2.d;
//std::cout << "d1:: " << d1 << " d2:: " << d2 << "\n";
if (sign(f) > 0) return sign(d2 - d1) >= 0 ? 0 : -1;
else {
//if (zero(d1)) return sign(d2) >= 0 ? 0 : -1;
//if (zero(d2)) return sign(d1) >= 0 ? 0 : -1;
//if (sign(d1) < 0 && sign(d2) < 0) return -2;
//if (sign(d1) > 0 && sign(d2) > 0) return 0;
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));
//std::cout << "p1:: " << p1 << "\n";
//std::cout << "p2:: " << p2 << "\n";
//std::cout << "q1:: " << q1 << "\n";
//std::cout << "v1:: " << v1 << "\n";
//std::cout << "dir:: " << dir << "\n";
//std::cout << "p0:: " << p0 << "\n";
l = Line3D(dir, p0);
return 1;
}
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;
//d *= -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++) {
//std::cout << "\nLOOP_START:::\n";
//std::cout << "LOOP_START:::\n";
//std::cout << "LOOP_START:::\n";
update_sc(S[i]);
Pos3D v = offset(S[i], O3D);
//std::cout << "dist:: " << dist(S[i], O3D) << "\n";
//std::cout << "v:: " << v << "\n";
//Pos3D w = { 2, 2, -2 };
//Pos w1 = convert(w, v);
//std::cout << w1 << "\n";
//std::cout << recover(w1, v) << " recover:: { 2, 2, -2 } \n";
Line3D l;
int f = 1;
Planes hp = B;
for (int j = 0; j < N; j++) {
if (i == j) continue;
f = intersection(S[i], S[j], l);
//std::cout << f << " ::f ::\n";
//std::cout << S[i].norm() * S[j].norm() << " ::n1 * n2 ::\n";
if (f == -2) { std::cout << "banana\n"; return; }
if (f < 0) break;
if (f == 0) continue;
//std::cout << "S[" << j << "]:: " << S[j] << "\n";
//std::cout << "l.p0:: " << l.p0 << "\nl.dir:: " << l.dir << "\n";
//std::cout << "dist:: i:: " << dist(S[i], l.p0) << "\n";
//std::cout << "dist:: j:: " << dist(S[j], l.p0) << "\n";
//std::cout << "dot:: i:: " << S[i].norm() * l.dir << "\n";
//std::cout << "dot:: j:: " << S[j].norm() * l.dir << "\n";
//std::cout << "mag:: l:: " << sign(l.dir.mag()) << "\n";
//std::cout << "v:: " << v << "\n";
Pos s = convert(l.p0, v);
Pos e = convert(l.p0 + l.dir, v);
//std::cout << "s:: " << s << "\ne:: " << e << "\n";
//std::cout << "vec:: " << e - s << "\n";
hp.push_back(Linear(s, e));
}
if (f == -1) continue;
//std::cout << "hpi\n";
Polygon hpi = half_plane_intersection(hp);
if (!hpi.size()) continue;
//std::cout << "hpii\n";
//std::cout << recover(hpi[0], S[i], v) << "\n";
//std::cout << hpi[0] << "\n";
//std::cout << "hpi:: \n";
//for (const Pos& p : hpi) std::cout << p << "\n";
//std::cout << "hpi:: \n";
Pos cen = centroid(hpi);
q = recover(cen, v);
l = { S[i].norm(), q };
q = intersection(S[i], l);
q = recover(hpi[0], v);
f0 = 1;
//for (int i = 0; i < ii; i++) {
// //std::cout << (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << " " << D_[i] << "\n";
// //std::cout << D_[i] - (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << "\n";
// ld dd = D_[i] - (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001);
// 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 << (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << " " << D_[i] << "\n";
//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);
if (D_[i] < dd) { f0 = 0; break; }
}
if (!f0) q = Pos3D(5.379084967, 0.000000000, 0.000000000);
std::cout << q << "\n";
}
else std::cout << "banana\n";
//q = Pos3D(2, 0, 2);
//for (const Plane& p : S) {
//std::cout << "dist:: " << dist(p, q) << "\n";
//}
return;
}
int main() { solve(); return 0; }//boj14118
//#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-7;
//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) { 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); }
////ld randTOL() {
//// ld rand01 = rand() / (ld)RAND_MAX;
//// ld err = (rand01 - .5) * TOL;
//// return err;
////}
////Pos3D add_noise(const Pos3D& p) {
//// ld rand01 = rand() / (ld)RAND_MAX;
//// ld err = (rand01 - .5) * TOL;
//// return p + Pos3D(randTOL(), randTOL(), randTOL());
////}
//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) {
// //std::cout << "pppp1:: " << p << "\n";
// //std::cout << "vvvv1:: " << v << "\n";
// p -= v;
// //std::cout << "pppp2:: " << p << "\n";
// p = rotate(p);
// //std::cout << "pppp3:: " << p << "\n";
// 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];
// //std::cout << "recover:: sc[2]:: " << sc[2] << "\n";
// //std::cout << "recover:: sc[3]:: " << sc[3] << "\n";
// //std::cout << "recover:: x:: " << x << "\n";
// //std::cout << "recover:: y:: " << y << "\n";
// //std::cout << "recover:: z:: " << z << "\n";
// Pos3D p = Pos3D(x * -sc[1] + y * sc[0], x * sc[0] + y * sc[1], z);
// //std::cout << "recover:: p:: " << p << "\n";
// 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);
// //std::cout << "intersection::\n";
// //std::cout << "t:: " << t << "\n";
// //std::cout << "S:: " << S << "\n";
// //std::cout << "l:: dir:: " << l.dir << " p0:: " << l.p0 << "\n";
// //std::cout << "inx:: " << l.p0 + (l.dir * t) << "\n";
// //std::cout << "intersection::\n";
// 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);
// //ld d1 = p1.d;
// //ld d2 = p2.d;
// //std::cout << "d1:: " << d1 << " d2:: " << d2 << "\n";
// if (sign(f) > 0) return sign(d2 - d1) >= 0 ? 0 : -1;
// else {
// //if (zero(d1)) return sign(d2) >= 0 ? 0 : -1;
// //if (zero(d2)) return sign(d1) >= 0 ? 0 : -1;
// //if (sign(d1) < 0 && sign(d2) < 0) return -2;
// //if (sign(d1) > 0 && sign(d2) > 0) return 0;
// 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));
// //std::cout << "p1:: " << p1 << "\n";
// //std::cout << "p2:: " << p2 << "\n";
// //std::cout << "q1:: " << q1 << "\n";
// //std::cout << "v1:: " << v1 << "\n";
// //std::cout << "dir:: " << dir << "\n";
// //std::cout << "p0:: " << p0 << "\n";
// l = Line3D(dir, p0);
// return 1;
//}
//int A_[LEN], B_[LEN], C_[LEN], D_[LEN];
//void solve() {
// std::cin.tie(0)->sync_with_stdio(0);
// std::cout.tie(0);
// std::cout << std::fixed;
// std::cout.precision(9);
// 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;
// ii++;
// int x = gcd(a, b, c, d);
// a /= x; b /= x; c /= x; d /= x;
// a *= -1; b *= -1; c *= -1;// d *= -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++) {
// //std::cout << "\nLOOP_START:::\n";
// //std::cout << "LOOP_START:::\n";
// //std::cout << "LOOP_START:::\n";
// update_sc(S[i]);
// Pos3D v = offset(S[i], O3D);
// //std::cout << "dist:: " << dist(S[i], O3D) << "\n";
// //std::cout << "v:: " << v << "\n";
// //Pos3D w = { 2, 2, -2 };
// //Pos w1 = convert(w, v);
// //std::cout << w1 << "\n";
// //std::cout << recover(w1, v) << " recover:: { 2, 2, -2 } \n";
// Line3D l;
// int f = 1;
// Planes hp = B;
// for (int j = 0; j < N; j++) {
// if (i == j) continue;
// f = intersection(S[i], S[j], l);
// //std::cout << f << " ::f ::\n";
// //std::cout << S[i].norm() * S[j].norm() << " ::n1 * n2 ::\n";
// if (f == -2) { std::cout << "banana\n"; return; }
// if (f < 0) break;
// if (f == 0) continue;
// //std::cout << "S[" << j << "]:: " << S[j] << "\n";
// //std::cout << "l.p0:: " << l.p0 << "\nl.dir:: " << l.dir << "\n";
// //std::cout << "dist:: i:: " << dist(S[i], l.p0) << "\n";
// //std::cout << "dist:: j:: " << dist(S[j], l.p0) << "\n";
// //std::cout << "dot:: i:: " << S[i].norm() * l.dir << "\n";
// //std::cout << "dot:: j:: " << S[j].norm() * l.dir << "\n";
// //std::cout << "mag:: l:: " << sign(l.dir.mag()) << "\n";
// //std::cout << "v:: " << v << "\n";
// Pos s = convert(l.p0, v);
// Pos e = convert(l.p0 + l.dir, v);
// //std::cout << "s:: " << s << "\ne:: " << e << "\n";
// //std::cout << "vec:: " << e - s << "\n";
// hp.push_back(Linear(s, e));
// }
// if (f == -1) continue;
// //std::cout << "hpi\n";
// Polygon hpi = half_plane_intersection(hp);
// if (!hpi.size()) continue;
// //std::cout << "hpii\n";
// //std::cout << recover(hpi[0], S[i], v) << "\n";
// //std::cout << hpi[0] << "\n";
// //std::cout << "hpi:: \n";
// //for (const Pos& p : hpi) std::cout << p << "\n";
// //std::cout << "hpi:: \n";
// Pos cen = centroid(hpi);
// q = recover(cen, v);
// //q = recover(hpi[0], v);
// f0 = 1;
// break;
// //return;
// }
// if (f0) {
// std::cout << q << "\n";
// //q = Pos3D(3.0, 5.0, 2.0);
// //q = Pos3D(1.5, 2.0, -5.0);
// for (const Plane& p : S) {
// //std::cout << "dist:: " << dist(p, q) << "\n";
// }
// for (int i = 0; i < ii; i++) {
// //std::cout << (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << " " << D_[i] << "\n";
// std::cout << D_[i] - (A_[i] * q.x + B_[i] * q.y + C_[i] * q.z - 0.001) << "\n";
// }
// }
// else std::cout << "banana\n";
// //q = Pos3D(2, 0, 2);
// //for (const Plane& p : S) {
// //std::cout << "dist:: " << dist(p, q) << "\n";
// //}
// return;
//}
//int main() { solve(); return 0; }//boj19508
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4376kb
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: 4288kb
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: 4288kb
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:
5.379084967000000 0.000000000000000 0.000000000000000
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 4388kb
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: 4384kb
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: 4288kb
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: 4228kb
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: 4344kb
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: 4132kb
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: 4264kb
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: 4072kb
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: 4324kb
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: 4064kb
input:
1 0 0 -1 -4
output:
-10000000.000000000000000 10000000.000000000000000 3.999999000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 4240kb
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: 4296kb
input:
1 1 0 0 -1000
output:
-999.999999000612323 -10000000.000000000000000 10000000.000000000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 4292kb
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: 4416kb
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: 4420kb
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: 4352kb
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: 4368kb
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: 0ms
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: 4372kb
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: 4324kb
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: -100
Wrong Answer
time: 1ms
memory: 4388kb
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:
5.379084967000000 0.000000000000000 0.000000000000000
result:
FAIL Condition failed: "A * X + B * Y + C * Z - 0.001 <= D"