백준 9212 (트라이앵글)

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;


#define EPS (1.0e-15)


class Vector3 {
public :
    double x, y, z;

    Vector3() {
        x = 0.0;
        y = 0.0;
        z = 0.0;
    }
    Vector3(double _x, double _y, double _z) {
        x = _x;
        y = _y;
        z = _z;
    }

    Vector3 operator+(const Vector3 &v) const {
        return Vector3(x + v.x, y + v.y, z + v.z);
    }
    Vector3 operator-(const Vector3 &v) const {
        return Vector3(x - v.x, y - v.y, z - v.z);
    }
    Vector3 operator*(const double &c) const {
        return Vector3(x * c, y * c, z * c);
    }
    double& operator[](int idx) {
        if (idx == 0)
            return x;
        else if (idx == 1)
            return y;
        else
            return z;
    }
    const double& operator[](int idx) const {
        if (idx == 0)
            return x;
        else if (idx == 1)
            return y;
        else
            return z;
    }

    double norm(void) const {
        return sqrt(x * x + y * y + z * z);
    }
    Vector3 unit(void) const {
        return *this * (1.0 / this->norm());
    }

    static double dot(const Vector3 &x, const Vector3 &y) {
        return x[0] * y[0] + x[1] * y[1] + x[2] * y[2];
    }
    static Vector3 cross(const Vector3 &x, const Vector3 &y) {
        return Vector3( x[1] * y[2] - x[2] * y[1],
                        x[2] * y[0] - x[0] * y[2],
                        x[0] * y[1] - x[1] * y[0]);
    }
    static bool eps_check(const Vector3 &v, double eps=0.0000000001) {
        return abs(v.x) < eps && abs(v.y) < eps && abs(v.z) < eps;
    }
};

class Line {
public:
    Vector3 p0, p1;

    Line(Vector3 _p0, Vector3 _p1) {
        p0 = _p0;
        p1 = _p1;
    }
};

class Triangle {
public:
    Vector3 p0, p1, p2;
    
    Triangle(Vector3 _p0, Vector3 _p1, Vector3 _p2) {
        p0 = _p0;
        p1 = _p1;
        p2 = _p2;
    }

    Vector3& operator[](int idx) {
        if (idx == 0)
            return p0;
        else if (idx == 1)
            return p1;
        else
            return p2;
    }
    const Vector3& operator[](int idx) const {
        if (idx == 0)
            return p0;
        else if (idx == 1)
            return p1;
        else
            return p2;
    }

    Vector3 centroid(void) const {
        return (p0 + p1 + p2) * (1.0 / 3.0);
    }
    
    static bool check_collision(Triangle tri, Line lin) {
        Vector3 n = Vector3::cross(tri.p0 - tri.p1, tri.p0 - tri.p2);
        Vector3 m = tri.p0;

        if (abs(Vector3::dot(n, lin.p0 - lin.p1)) < EPS)
            return false;

        // line : l.p0 * t + l.p1 * (1 - t)
        double t = Vector3::dot(n, m - lin.p1) / Vector3::dot(n, lin.p0 - lin.p1);
        
        Vector3 p = lin.p0 * t + lin.p1 * (1.0 - t);

        if (t < EPS || 1.0 - EPS < t)
            return false;


        // line collision check
        Line chk(tri.centroid(), p);

        if (Vector3::eps_check(chk.p0 - chk.p1, EPS))
            return true;
        
        else {
            bool out = false;

            for (int i = 0; i < 3; i++) {
                Line temp_line = Line(tri[i], tri[(i+1)%3]);

                Vector3 a = chk.p0 - chk.p1, b = temp_line.p1 - temp_line.p0, c = temp_line.p1 - chk.p1;
                // a * t + b * k = c
                t = (c.y * b.x - c.x * b.y) / (a.y * b.x - a.x * b.y);

                out = out || (EPS < t && t < 1.0 - EPS);
            }

            return !out;
        }
    }
};


typedef Vector3 Vec3;
typedef Triangle Tri;

bool solve(Tri tri1, Tri tri2) {
    Line lin(tri2[0], tri2[1]);

    bool flag1 =    Tri::check_collision(tri1, Line(tri2[0], tri2[1])) ||
                    Tri::check_collision(tri1, Line(tri2[1], tri2[2])) ||
                    Tri::check_collision(tri1, Line(tri2[2], tri2[0]));
    
    bool flag2 =    Tri::check_collision(tri2, Line(tri1[0], tri1[1])) || 
                    Tri::check_collision(tri2, Line(tri1[1], tri1[2])) ||
                    Tri::check_collision(tri2, Line(tri1[2], tri1[0]));
    
    return flag1 && flag2;
}

int main(void) {
    int t;
    scanf("%d", &t);

    while (t--) {
        Vec3 p1, p2, p3;
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf", &p1.x, &p1.y, &p1.z, &p2.x, &p2.y, &p2.z, &p3.x, &p3.y, &p3.z);
        Tri tri1(p1, p2, p3);
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf", &p1.x, &p1.y, &p1.z, &p2.x, &p2.y, &p2.z, &p3.x, &p3.y, &p3.z);
        Tri tri2(p1, p2, p3);
        
        printf("%s\n", solve(tri1, tri2) ? "YES" : "NO");
    }

    system("pause");
    return 0;
}