Fivt_3/task-B/23.11.2017

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <cassert>


struct Point {
    int  x;
    int  y;
    int  z;
    int number;
    Point(int _x, int _y, int _z, int _number = 0):
            x(_x),
            y(_y),
            z(_z),
            number(_number)
    {
    }
    bool operator==(const Point& other) const;
    bool operator!=(const Point& other) const;
    Point operator-(const Point& other) const;
    double operator^(int p) const;
    double operator*(const Point& other) const;
    Point OtherPointFromSet(const std::vector<Point>& points);
};


bool Point::operator==(const Point &other) const{
    return (this->x == other.x && this->y == other.y && this->z == other.z);
}


bool Point::operator!=(const Point &other) const{
    return (this->x != other.x || this->y != other.y || this->z != other.z);
}

Point Point::operator-(const Point& other) const{
    return {this->x - other.x, this->y - other.y, this->z - other.z};
}


double Point::operator^(int p) const{
    return std::pow(this->x,p) + std::pow(this->y,p) + std::pow(this->z,p);
}


double Point::operator*(const Point &other) const{
    return (this->x*other.x + this->y*other.y + this->z*other.z);
}

Point Point::OtherPointFromSet(const std::vector<Point> &points) {
    assert(points.size() != 0);
    for(auto point: points ) {
        if (point != *this) {
            return point;
        }
    }
}


Point VectorMultiplication(const Point& p1, const Point& p2) {
    return {p1.y*p2.z - p1.z*p2.y, - (p1.x*p2.z - p1.z*p2.x ), p1.x*p2.y - p1.y*p2.x};
}

double Distance(const Point& p1, const Point& p2) {
    return std::sqrt( (p1-p2)^2 );
}


double OzAngle(const Point& p1, const Point& p2) {
    Point Oz (0,0,1);
    Point p12  = p2 - p1;
    double t = (p12*Oz)/std::sqrt((p12*p12)*(Oz*Oz));
    if (t < -1) {
        t = -1;
    }
    else if(t > 1) {
        t = 1;
    }
    double acos = std::acos(t);
    return acos;
}

// ??
// дост ли самой нижней??
Point MostBottom(std::vector<Point> &points) {
    Point point_min = points[0];
    for (auto point: points) {
        if (point.z < point_min.z) {
            point_min = point;
        }
    }
    return point_min;
}

template <class Triangle>
struct Edge {
    Point p1;
    Point p2;
    bool IsProcessed;
    Triangle* triangle;
    Edge(Point _p1, Point _p2, Triangle* _triangle);
    Point PivotAroundEdge(std::vector<Point>& points, const Point& forbidden_point);
    Point PivotAroundEdge(std::vector<Point> &points);
    Point GetForbiddenPoint() const;
    bool operator==(const Edge& other);
};


template <class Triangle>
Edge<Triangle>::Edge(Point _p1, Point _p2, Triangle* _triangle) :
        p1(_p1),
        p2(_p2),
        IsProcessed(false),
        triangle(_triangle)
{
}


template <class Triangle>
bool Edge<Triangle>::operator==(const Edge<Triangle> &other) {
    return (this->p1 == other.p1 && this->p2 == other.p2);
}


template <class Triangle>
Point Edge<Triangle>::GetForbiddenPoint() const {
    for (auto point: triangle->GetPoints()) {
        if (point != p1 && point != p2) {
            return  point;
        }
    }
    throw "GetForbiddenPoint ERROR";
}


struct Triangle {
    Edge<Triangle> edge12;
    Edge<Triangle> edge23;
    Edge<Triangle> edge31;
    std::vector<Edge<Triangle>>GetEdges() const;
    std::vector<Point> GetPoints() const;
    Triangle(const Edge<Triangle>& edge1, const Point& point);
    Triangle(const Edge<Triangle>& edge1, const Edge<Triangle>& edge2, const Edge<Triangle>& edge3);
//  std::vector<Point> ProperOrder();
};

Triangle::Triangle(const Edge<Triangle> &edge, const Point &point) :
    edge12(edge),
    edge23(Edge<Triangle>(edge.p1, point, this)), //??
    edge31(Edge<Triangle>(edge.p2, point, this)) //??
{
}


Triangle::Triangle(const Edge<Triangle> &edge1, const Edge<Triangle> &edge2, const Edge<Triangle> &edge3) :
    edge12(edge1),
    edge23(edge2),
    edge31 (edge3)
{
}

std::vector<Point> Triangle::GetPoints() const{
    std::vector<Point> points = {edge12.p1, edge12.p2, edge23.p1, edge23.p2, edge31.p1, edge31.p2 };
    for (int i = 0; i < points.size(); ++i) {
        for (int j = 0; j < points.size(); ++j) {
            if (points[i] == points[j] && i != j) {
                points.erase(points.begin() + j);
                break;
            }
        }
    }
    return points;
}

std::vector<Edge<Triangle>> Triangle::GetEdges() const{
    std::vector<Edge<Triangle>> edges = {edge12,edge23,edge31};
    return edges;
}


double FindOutFaceD(double A, double B, double C, const Point& pivot) {
    return -( A*pivot.x + B*pivot.y + C*pivot.z );
}

bool IsFace(const Triangle& triangle, const std::vector<Point>& points) { // O(n)
    const std::vector<Point> triangles_points = triangle.GetPoints();
    Point v1 = triangles_points[1] - triangles_points[0];
    Point v2 = triangles_points[2] - triangles_points[0];
    Point normal (VectorMultiplication(v1,v2));
    double D_of_triangle = FindOutFaceD(normal.x, normal.y, normal.z, triangles_points[0]);
    std::vector<double> D_of_other_points;
    for (auto point: points) {
        if ( (point !=  triangles_points[1] && point !=  triangles_points[2]) && point !=  triangles_points[0]) {
            double D = FindOutFaceD(normal.x, normal.y, normal.z, point);
            D_of_other_points.push_back(D);
        }
    }
    double min_element = *std::min_element(D_of_other_points.begin(), D_of_other_points.end());
    double max_element = *std::max_element(D_of_other_points.begin(), D_of_other_points.end());
    bool result = (D_of_triangle < min_element ||
            D_of_triangle > max_element ) ;
    return result;
}



Edge<Triangle> FindEdgeOnHull(std::vector<Point>& points) {
    Point p1 = MostBottom(points);
    Point p2 = p1.OtherPointFromSet(points);
    for (auto point: points) {
        if ( p1 != point && OzAngle(p1,point) >= OzAngle(p1,p2) ) {
            p2 = point;
        }
    }
    return {p1,p2, nullptr};
}

Triangle FindtTriangleOnHull(std::vector<Point>& points) {
    Edge<Triangle> edge = FindEdgeOnHull(points);
    Point pivot = edge.PivotAroundEdge(points);
    return Triangle(edge, pivot); //тут можно не запоминать
}



// вернет такую точку, что получилась грань
template <class Triangle>
Point Edge<Triangle>::PivotAroundEdge(std::vector<Point> &points, const Point& forbidden_point) { // O(n^2)
    assert(points.size() > 2); // не должно быть совпад
    Point p1 = this->p1;
    Point p2 = this->p2;
    double current_angle = 0;
    for (auto point: points) {
        if ((point != p1 && point != p2) && point != forbidden_point) {
            Edge<Triangle> this_edge = *this;
            Triangle triangle (this_edge, point);
            if (IsFace(triangle, points)) { // O(n)
                this->IsProcessed = true; //??
                return point;
            }
        }
    }
}

template <class Triangle>
Point Edge<Triangle>::PivotAroundEdge(std::vector<Point> &points) { // O(n^2)
    assert(points.size() > 2); // не должно быть совпад
    Point p1 = this->p1;
    Point p2 = this->p2;
    double current_angle = 0;
    for (auto point: points) {
        if ((point != p1 && point != p2)) {
            Edge<Triangle> this_edge = *this;
            Triangle triangle (this_edge, point);
            if (IsFace(triangle, points)) { // O(n)
                return point;
            }
        }
    }
}


bool IsNotUsedEdges(std::vector<Edge<Triangle>> edges) {
    bool result = true;
    for (auto edge: edges) {
        result = result && edge.IsProcessed;
    }
    return  !result;
}

template <class T>
bool IsIn(T myelement, std::vector<T>& elements) {
    for (auto element: elements) {
        if (myelement == element) {
            return true;
        }
    }
    return  false;
}


void GiftWrapping(std::vector<Point>& points, std::vector<Triangle>& faces) {
    Triangle t = FindtTriangleOnHull(points);
    faces.push_back(t);
    std::vector<Edge<Triangle>> edges = t.GetEdges(); // начальная хуйня
    while (IsNotUsedEdges(edges)) { // O(n)
        Edge<Triangle>& newedge = edges.back();
//      edges.pop_back();
        if (!newedge.IsProcessed) {
            Point pivot = newedge.PivotAroundEdge(points, newedge.GetForbiddenPoint());
            Triangle newtriangle (newedge, pivot); //O(n)
            for (auto triangles_edge: newtriangle.GetEdges()) {
                if (!IsIn(triangles_edge, edges)) { // таких еще нету
                    edges.push_back(triangles_edge);
                }
            }
            faces.push_back(newtriangle); // IsIn??
            std::cout<<faces.size()<<std::endl;
        }
    }
}

int main() {

    Point p1 (1,0,0);
    Point p2 (0,1,0);
    Point p3 (0,0,1);
    Point p4 (0,0,0);
//  Point p5 (1,0,-1);

    std::vector<Point> points = {p1,p2,p3,p4};
    std::vector<Triangle> faces;

    GiftWrapping(points, faces);


//  std::cout<<OzAngle(p1,p2);
//  std::cout<<' ';
//  std::cout<<OzAngle(p1,p5);



    return  0;
}



//  int m; // число тестов
//  std::cin>>m;
//
//  for (int i = 0; i < m; ++i) {
//      int n; // число точек
//      std::cin>>n;
//      std::vector<Point> points;
//      std::vector<Triangle> faces;
//      for (int j = 0; j < n; ++j) {
//          int x,y,z;
//          std::cin>>x>>y>>z;
//          points.emplace_back(Point(x,y,z,j));
//      }
//      GiftWrapping(points, faces);
//      std::cout<<faces.size()<<std::endl;
//      for (auto face: faces) {
//          std::cout<<3<<' ';
//          for (auto point: face.ProperOrder()) {
//              std::cout<<point.number<<' ';
//          }
//          std::cout<<'\n';
//      }
//  }