// implement 47min #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-8; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include typedef complex Point; typedef vector Polygon; static const double INF = 1e+10; #define CURR(P, i) (P[i]) #define NEXT(P, i) (P[(i + 1) % P.size()]) struct Line : public vector { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; struct Circle { Point p; double r; Circle() {;} Circle(Point p, double r) : p(p), r(r) {;} }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } inline double cross(const Point &a, const Point &b) { return imag(conj(a) * b); } inline double dot(const Point &a, const Point &b) { return real(conj(a) * b); } inline int ccw(Point a, Point b, Point c) { b -= a; c -= a; if (cross(b, c) > 0) { return 1; } if (cross(b, c) < 0) { return -1; } if (dot(b, c) < 0) { return 2; } if (norm(b) < norm(c)) { return -2; } return 0; } Point projection(const Line &l, const Point &p) { double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]); return l[0] + t * (l[0] - l[1]); } vector crosspointLC(const Line &l, const Circle &c) { vector ret; Point center = projection(l, c.p); double d = abs(center - c.p); double t = sqrt(c.r * c.r - d * d); if (isnan(t)) { return ret; } Point vect = (l[1] - l[0]); vect /= abs(vect); ret.push_back(center - vect * t); if (t > EPS) { ret.push_back(center + vect * t); } return ret; } // valarrayはサイズが同じでないとコピーが上手く働かないので注意。 // Point p; // p = a - b; // といったコードはバグる。 // グローバル変数にも注意。 template struct Vector { vector vect; Vector() {;} explicit Vector(int length) : vect(length) {;} Vector(T x, T y) : vect(2) { vect[0] = x; vect[1] = y; } Vector(T x, T y, T z) : vect(3) { vect[0] = x; vect[1] = y; vect[2] = z; } Vector(T x, T y, T z, T w) : vect(4) { vect[0] = x; vect[1] = y; vect[2] = z; vect[3] = w; } int size() const { return vect.size(); } T operator[](int index) const { assert(index >= 0 && index < size()); return vect[index]; } T &operator[](int index) { assert(index >= 0 && index < size()); return vect[index]; } Vector operator+(const Vector &rhs) const { assert(size() == rhs.size()); Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] += rhs.vect[i]; } return ret; } Vector operator-(const Vector &rhs) const { assert(size() == rhs.size()); Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] -= rhs.vect[i]; } return ret; } Vector operator+(const T &rhs) const { Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] += rhs; } return ret; } Vector operator-(const T &rhs) const { Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] -= rhs; } return ret; } Vector operator*(const T &rhs) const { Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] *= rhs; } return ret; } Vector operator/(const T &rhs) const { Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] /= rhs; } return ret; } Vector operator%(const T &rhs) const { Vector ret = *this; for (int i = 0; i < size(); i++) { ret.vect[i] %= rhs; } return ret; } Vector &operator+=(const Vector &rhs) { return *this = *this + rhs; } Vector &operator-=(const Vector &rhs) { return *this = *this - rhs; } Vector &operator+=(const T &rhs) { return *this = *this + rhs; } Vector &operator-=(const T &rhs) { return *this = *this - rhs; } Vector &operator*=(const T &rhs) { return *this = *this * rhs; } Vector &operator/=(const T &rhs) { return *this = *this / rhs; } Vector &operator%=(const T &rhs) { return *this = *this % rhs; } Vector operator-() const { return *this * -1; } T X() const { assert(size() >= 1); return vect[0]; } T Y() const { assert(size() >= 2); return vect[1]; } T Z() const { assert(size() >= 3); return vect[2]; } T W() const { assert(size() >= 4); return vect[3]; } T &X() { assert(size() >= 1); return vect[0]; } T &Y() { assert(size() >= 2); return vect[1]; } T &Z() { assert(size() >= 3); return vect[2]; } T &W() { assert(size() >= 4); return vect[3]; } T dot(const Vector &rhs) const { assert(size() == rhs.size()); T ret = 0; for (int i = 0; i < size(); i++) { ret += vect[i] * rhs.vect[i]; } return ret; } Vector cross(const Vector &rhs) const { assert(size() == 3); assert(rhs.size() == 3); Vector ret = Vector(3); ret.X() = this->Y() * rhs.Z() - this->Z() * rhs.Y(); ret.Y() = this->Z() * rhs.X() - this->X() * rhs.Z(); ret.Z() = this->X() * rhs.Y() - this->Y() * rhs.X(); return ret; } T norm() const { return dot(*this); } double abs() const { return sqrt(norm()); } Vector &normalize() { return *this/ abs(*this); } void Print() const { for (int i = 0; i < size(); i++) { cout << vect[i] << " "; } cout << endl; } }; template ostream &operator<<(ostream &os, const Vector &rhs) { for (int i = 0; i < rhs.size(); i++) { os << rhs.vect[i] << " "; } //os << endl; return os; } template T dot(const Vector &lhs, const Vector &rhs) { return lhs.dot(rhs); } template Vector cross(const Vector &lhs, const Vector &rhs) { return lhs.cross(rhs); } template struct Matrix { vector > vects; Matrix() {;} Matrix(int height, int width) : vects(height, Vector(width)) {;} Matrix(const Matrix &A, const Matrix &B, const Matrix &C, const Matrix &D) { assert(A.width() == C.width()); assert(A.height() == B.height()); assert(B.width() == D.width()); assert(C.height() == D.height()); vects = vector >(A.height() + C.height(), Vector(A.width() + B.width())); SetMatrix(0, 0, A); SetMatrix(0, A.width(), B); SetMatrix(A.height(), 0, C); SetMatrix(A.height(), A.width(), D); } static Matrix I(int s) { Matrix ret(s, s); for (int i = 0; i < s; i++) { ret[i][i] = 1; } return ret; } int size() const { return vects.size(); } int height() const { return size(); } int width() const { return vects[0].size(); } void SetMatrix(int sy, int sx, const Matrix &matrix) { assert(sx >= 0 && sx + matrix.width() <= width()); assert(sy >= 0 && sy + matrix.height() <= height()); for (int y = 0; y < matrix.height(); y++) { for (int x = 0; x < matrix.width(); x++) { vects[sy + y][sx + x] = matrix.vects[y][x]; } } } Matrix GetMatrix(int sy, int sx, int w, int h) const { assert(sx >= 0 && sx + w <= width()); assert(sy >= 0 && sy + h <= height()); Matrix ret(h, w); for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { ret.vects[y][x] = vects[sy + y][sx + x]; } } return ret; } Vector operator[](int index) const { assert(index >= 0 && index < size()); return vects[index]; } Vector &operator[](int index) { assert(index >= 0 && index < size()); return vects[index]; } Vector operator*(const Vector &rhs) const { assert(size() == rhs.size()); Vector ret(size()); for (int y = 0; y < size(); y++) { ret[y] = dot(vects[y], rhs); } return ret; } Matrix operator+(const Matrix &rhs) const { Matrix ret = *this; for (int i = 0; i < ret.size(); i++) { ret.vects[i] += rhs.vects[i]; } return ret; } Matrix operator-(const Matrix &rhs) const { Matrix ret = *this; for (int i = 0; i < ret.size(); i++) { ret.vects[i] -= rhs.vects[i]; } return ret; } Matrix operator*(const Matrix &rhs) const { assert(width() == rhs.height()); Matrix ret(height(), rhs.width()); for (int i = 0; i < height(); i++) { for (int k = 0; k < width(); k++) { for (int j = 0; j < rhs.width(); j++) { T prev = ret[i][j]; T mul = vects[i][k] * rhs.vects[k][j]; assert("overflow!" && (rhs.vects[k][j] == 0 || mul / rhs.vects[k][j] == vects[i][k])); assert("overflow!" && mul > 0 ? prev + mul >= prev : prev + mul <= prev); ret[i][j] += vects[i][k] * rhs.vects[k][j]; } } } return ret; } Matrix operator+(const T &rhs) const { Matrix ret = *this; for (int i = 0; i < size(); i++) { ret.vects[i] += rhs; } return ret; } Matrix operator-(const T &rhs) const { Matrix ret = *this; for (int i = 0; i < size(); i++) { ret.vects[i] -= rhs; } return ret; } Matrix operator*(const T &rhs) const { Matrix ret = *this; for (int i = 0; i < size(); i++) { ret.vects[i] *= rhs; } return ret; } Matrix operator/(const T &rhs) const { Matrix ret = *this; for (int i = 0; i < size(); i++) { ret.vects[i] /= rhs; } return ret; } Matrix operator%(const T &rhs) const { Matrix ret = *this; for (int i = 0; i < size(); i++) { ret.vects[i] %= rhs; } return ret; } Matrix &operator+=(const Matrix &rhs) { return *this = *this + rhs; } Matrix &operator-=(const Matrix &rhs) { return *this = *this - rhs; } Matrix &operator*=(const Matrix &rhs) { return *this = *this * rhs; } Matrix &operator+=(const T &rhs) { return *this = *this + rhs; } Matrix &operator-=(const T &rhs) { return *this = *this - rhs; } Matrix &operator*=(const T &rhs) { return *this = *this * rhs; } Matrix &operator/=(const T &rhs) { return *this = *this / rhs; } Matrix &operator%=(const T &rhs) { return *this = *this % rhs; } Matrix operator-() const { return *this * -1; } Vector colum(int x) { assert(x >= 0 && x < width()); Vector ret(height()); for (int y = 0; y < height(); y++) { ret[y] = vects[y][x]; } return ret; } T trace() const { T ret = 0; for (int i = 0; i < size(); i++) { ret += vects[i][i]; } return ret; } Matrix transpose() const { Matrix ret(width(), height()); for (int y = 0; y < height(); y++) { for (int x = 0; x < width(); y++) { ret[x][y] = vects[y][x]; } } return ret; } Matrix adjoint() const { assert(size() == 3); Matrix ret(3, 3); ret[0] = cross(vects[1], vects[2]); ret[1] = cross(vects[2], vects[0]); ret[2] = cross(vects[0], vects[1]); return ret; } Matrix inverse() const { assert(size() == 3); Matrix ret(3, 3); Matrix A = adjoint(); T d = dot(A[0], vects[0]); if (d == 0.0) { return ret; } return A.transpose() / d; } T det() const { assert(size() == 3); return dot(vects[0], cross(vects[1], vects[2])); } void Print() { for (int i = 0; i < size(); i++) { vects[i].Print(); } } }; template ostream &operator<<(ostream &os, const Matrix &rhs) { for (int i = 0; i < rhs.size(); i++) { os << rhs.vects[i] << endl; } return os; } typedef Vector Point3D; inline double Norm(const Point3D &p) { return dot(p, p); } inline double Abs(const Point3D &p) { return sqrt(dot(p, p)); } //=================================================================== enum ANS { INVALID, YES, NO, }; ANS Solver(Point3D c1, Point3D c2, Point3D t1[3], Point3D t2[3]) { Point3D e1[3] = { t1[0], t1[1], t1[2] }; Point3D e2[3] = { t2[0], t2[1], t2[2] }; Matrix rot(3, 3); REP(y, 3) { REP(x, 3) { rot[y][x] = e1[y][x]; } } c1 = rot * c1; c2 = rot * c2; REP(i, 3) { e1[i] = rot * e1[i]; e2[i] = rot * e2[i]; } c2 -= c1; c1 -= c1; if (fabs(c2.Z()) > 1.0f) { return NO; } if (fabs(e2[0].Z()) < EPS && fabs(e2[1].Z()) < EPS) { // coplaner if (fabs(c2.Z()) < EPS && Abs(c2) - 2.0f < EPS) { return INVALID; } return NO; } double d = -dot(c2, e2[2]); Point p1(-d / e2[2].X(), 0); Point p2(0, -d / e2[2].Y()); if (isinf(p1.real()) || isnan(p1.real())) { p1 = Point(1, -d / e2[2].Y()); } if (isinf(p2.imag()) || isnan(p2.imag())) { p2 = Point(-d / e2[2].X(), 1); } Line l(p1, p2); Circle circle(Point(c2.X(), c2.Y()), sqrt(1.0f - c2.Z() * c2.Z())); vector ans = crosspointLC(l, circle); if (ans.size() == 0) { return NO; } if (ans.size() == 1) { if (fabs(abs(ans[0]) - 1.0f) < EPS) { return INVALID; } return NO; } if (ans.size() == 2) { if (fabs(abs(ans[0]) - 1.0f) < EPS) { return INVALID; } if (fabs(abs(ans[1]) - 1.0f) < EPS) { return INVALID; } bool ok = (abs(ans[0]) < 1.0f) != (abs(ans[1]) < 1.0f); return ok ? YES : NO; } assert(false); return NO; } void GetRing(Point3D &c, Point3D e[3]) { double x, y, z; scanf("%lf %lf %lf", &x, &y, &z); c = Point3D(x, y, z); scanf("%lf %lf %lf", &x, &y, &z); e[0] = Point3D(x, y, z); scanf("%lf %lf %lf", &x, &y, &z); e[1] = Point3D(x, y, z); e[2] = cross(e[0], e[1]); e[2] /= Abs(e[2]); } int main() { Point3D c1, c2; Point3D e1[3]; Point3D e2[3]; GetRing(c1, e1); GetRing(c2, e2); ANS ans = Solver(c1, c2, e1, e2); assert(ans != INVALID); if (ans == YES) { puts("YES"); } else { puts("NO"); } }