#include <set>
#include <map>
#include <fstream>
#include <iostream>
#include <chrono>
#include <memory>
#include <vector>
#include <cmath>
#include <list>

static std::string IN_FILE = "points_uniq.txt";
static double NORM_ZERO = 1e-9;
static double ZERO = 1e-15;

class Point3D {

public:
    int id;

private:
    double x;
    double y;
    double z;

public:
    Point3D() : Point3D(0.0, 0.0, 0.0) {}
    Point3D(int iid, double ix, double iy, double iz) : id(iid), x(ix), y(iy), z(iz) {}

    Point3D(double x, double y, double z) :Point3D(-1, x, y, z) {}

    bool operator== (const Point3D & x) const {
        return id == x.id;
    }

    Point3D neg() const {
        return Point3D(-x, -y, -z);
    }

    static Point3D add(std::initializer_list<Point3D> pts) {
        double x = 0.0;
        double y = 0.0;
        double z = 0.0;
        for (const Point3D& pt : pts) {
            x += pt.x;
            y += pt.y;
            z += pt.z;
        }
        return Point3D(x, y, z);
    }

    static Point3D sub(const Point3D& a, const Point3D& b) {
        return Point3D(a.x - b.x, a.y - b.y, a.z - b.z);
    }

    Point3D mul(double d) const {
        return Point3D(x * d, y * d, z * d);
    }

    static double scal(const Point3D& a, const Point3D& b) {
        return a.x * b.x + a.y * b.y + a.z * b.z;
    }

    static Point3D prod(const Point3D& a, const Point3D& b) {
        double x = a.y * b.z - a.z * b.y;
        double y = a.z * b.x - a.x * b.z;
        double z = a.x * b.y - a.y * b.x;

        return Point3D(x, y, z);
    }

    double size() const {
        double d = scal(*this, *this);
        return sqrt(d);
    }

    Point3D norm() const {
        double d = size();
        if (d < ZERO)
            return *this;
        return mul(1.0 / d);
    }
};

class Line {

    Point3D a;
    Point3D b;
    bool mark;

public:
    Line(const Point3D& ia, const Point3D& ib): a(ia), b(ib), mark(false) {}

    void doMark() {
        mark = !mark;
    }

    bool isMark() const {
        return mark;
    }

    Point3D beg() const {
        return a;
    }

    Point3D end() const {
        return b;
    }

    Point3D beg(bool rev) const {
        return rev ? b : a;
    }

    Point3D end(bool rev) const {
        return rev ? a : b;
    }

    Point3D dir(bool rev) const {
        Point3D d = Point3D::sub(b, a);
        return rev ? d.neg() : d;
    }

    void addIDs(std::set<int> & pts) const {
        pts.insert(a.id);
        pts.insert(b.id);
    }
};

class Triangle {

    Point3D norm;
    std::shared_ptr<Line> a;
    std::shared_ptr<Line> b;
    std::shared_ptr<Line> c;
    bool arev;
    bool brev;
    bool crev;

public:
    Triangle(const Point3D& a, const Point3D& b, const Point3D& c, Point3D * p) : Triangle(std::make_shared<Line>(a, b), std::make_shared<Line>(b, c), std::make_shared<Line>(c, a), p) {}

    Triangle(std::shared_ptr<Line> a, std::shared_ptr<Line> b, std::shared_ptr<Line> c, Point3D * p) : Triangle(a, b, c, p, false, false) {}

    Triangle(std::shared_ptr<Line> ia, std::shared_ptr<Line> ib, std::shared_ptr<Line> ic, Point3D * p, bool iarev, bool icrev) : a(ia), b(ib), c(ic), arev(iarev), crev(icrev), norm(0, 0, 0) {
        brev = a->end(arev) == b->end();

        bool ba = a->beg(arev) == c->end(crev);
        bool bb = b->beg(brev) == a->end(arev);
        bool bc = c->beg(crev) == b->end(brev);
        if (!(ba && bb && bc))
            std::cout << "failed ori\n";

        Point3D da = a->dir(arev);
        Point3D dc = c->dir(!crev);

        Point3D n = Point3D::prod(da, dc);
        if (p != nullptr) {
            double d = Point3D::scal(n, Point3D::sub(*p, a->beg()));
            if (d < 0)
                n = n.mul(-1);
            if (fabs(d) < NORM_ZERO)
                std::cout << "inv norm " << d << "\n";
        }
        norm = n.norm();
    }

    bool isValid() const {
        return Point3D::scal(norm, norm) > 1e-5;
    }

    double getOri(const Point3D& p) const {
        auto diff = Point3D::sub(p, a->beg());
        auto sc = Point3D::scal(norm, diff);
        return sc;
    }

    void marklines() {
        a.get()->doMark();
        b.get()->doMark();
        c.get()->doMark();
    }

    void addMarked(std::vector<std::shared_ptr<Line>> & bord) {
        if (a.get()->isMark())
            bord.push_back(a);
        if (b.get()->isMark())
            bord.push_back(b);
        if (c.get()->isMark())
            bord.push_back(c);
    }

    void addIDs(std::set<int> & pts) {
        a->addIDs(pts);
        b->addIDs(pts);
        c->addIDs(pts);
    }
};

class Envelope {

    Point3D in;
    std::list<Triangle> tri;

public:
    Envelope(const Point3D& iin, std::shared_ptr<Triangle> tr) : in(iin) {
        tri.push_back(*tr);
    }

    void addPoint(const Point3D& pt) {
        auto tr = tri.begin();
        auto trEnd = tri.end();
        while (tr != trEnd)
        {
            auto& triangle = *tr;
            if (triangle.getOri(pt) < NORM_ZERO) {
                tr = tri.erase(tr);
            }
            else {
                triangle.marklines();
                ++tr;
            }
        }

        std::vector<std::shared_ptr<Line>> bord;
        for (auto& tr : tri)
            tr.addMarked(bord);

        std::map<int, std::shared_ptr<Line>> map;
        for (auto lin : bord) {
            Point3D b = lin->beg(false);
            Point3D e = lin->end(false);

            std::shared_ptr<Line>& x = map[b.id];
            if (x == nullptr) {
                x = std::make_shared<Line>(pt, b);
            }
            bool xrev = x->end() == pt;

            std::shared_ptr<Line>& z = map[e.id];
            if (z == nullptr) {
                z = std::make_shared<Line>(e, pt);
            }
            bool zrev = z->beg() == pt;

            Triangle tr(x, lin, z, &in, xrev, zrev);
            if (tr.isValid())
                tri.push_back(tr);
            else
                std::cout << "inv triangle" << "\n";
            lin->doMark();
        }
    }

    size_t getPtCnt() {
        std::set<int> pts;
        for (auto& tr : tri)
            tr.addIDs(pts);

        return pts.size();
    }

    size_t getTriCnt() {
        return tri.size();
    }

};

static int ptCnt;

Point3D getPoint(std::istream & sc) {
    std::string line;
    std::getline(sc, line);
    if (sc.eof())
        return Point3D();
    double x, y, z;
    if (sscanf(line.c_str(), "%lf %lf %lf", &x, &y, &z) != 3)
        return Point3D();
    return Point3D(++ptCnt, x, y, z);
}

Envelope * initEnvelope(std::istream & sc) {
    Point3D a = getPoint(sc);
    Point3D b = getPoint(sc);

    std::vector<Point3D> pts;

    Point3D c(0.0,0.0,0.0);

    std::unique_ptr<Triangle> tr = nullptr;
    while (!sc.eof()) {
        c = getPoint(sc);
        tr.reset(new Triangle(a, b, c, nullptr));
        if (tr->isValid())
            break;
        pts.push_back(c);
    }

    // TODO: if !tr valid
    Point3D d(0.0,0.0,0.0);
    while (!sc.eof()) {
        d = getPoint(sc);
        double n = tr->getOri(d);
        if (fabs(n) > NORM_ZERO)
            break;
        pts.push_back(d);
    }

    Point3D in = Point3D::add({ a, b, c, d }).mul(1 / 4.0);
    Envelope * env = new Envelope(in, std::make_shared<Triangle>(a, b, c, &in));
    env->addPoint(d);

    for (const Point3D& pt : pts)
        env->addPoint(pt);
    return env;
}

using namespace std::chrono;

int main() {
    ptCnt = 0;

    for (int i = 0; i < 20; i++) {
        std::ifstream sc(IN_FILE);

        auto start = high_resolution_clock::now();
        Envelope * env = initEnvelope(sc);

        while (!sc.eof()) {
            Point3D pt = getPoint(sc);
            if (pt.id >= 0)
                env->addPoint(pt);
        }
        auto end = high_resolution_clock::now();
        sc.close();

        auto diff = duration_cast<duration<double>>(end - start);

        std::cout << "poly cnt: " << env->getTriCnt() << " pt cnt: " << ptCnt << " pts: " << env->getPtCnt() << "\n";

        delete env;
    }
    return 0;
}