Fivt_3/task-B/25.11.2017 (2'st test)

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


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)
    {
    }

    Point(const Point& other) {
        x = other.x;
        y = other.y;
        z = other.z;
        number = other.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;
    double GetModule() const;
    void Print() const;
};


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 OtherPointFromSet(const Point& this_point, const std::vector<Point> &points) {
    if (points.empty()) {
        std::cerr<<" points is empty";
        exit(1);
    }
    for(const auto& point: points ) {
        if (point != this_point) {
            return point;
        }
    }
    std::cerr<<"NO OtherPointFromSet";
    exit(1);
}

double Point::GetModule() const {
    return std::sqrt( this->x*this->x + this->y*this->y + this->z*this->z );
}


void Point::Print() const {
    std::cout<<this->x<<' '<<this->y<<' '<<this->z;
    std::cout<<'\n';
}


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 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(const std::vector<Point>& points) {
    Point point_min = points[0];
    for (const auto& point: points) {
        if (point.z < point_min.z) {
            point_min = point;
        }
    }
    return point_min;
}


struct Edge {
    Point p1;
    Point p2;
    Point forbidden_point;
    bool IsProcessed;
    Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point);
    Edge(const Edge& edge, const Point& _forbidden_point);
    Edge(const Edge& edge);
    Point PivotAroundEdge(const std::vector<Point> &points);
    bool operator==(const Edge& other) const;
};


Edge::Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point) :
        p1(_p1),
        p2(_p2),
        forbidden_point(_forbidden_point),
        IsProcessed(false)
{
}


Edge::Edge(const Edge& edge, const Point& _forbidden_point) :
    p1(edge.p1),
    p2(edge.p2),
    forbidden_point(_forbidden_point),
    IsProcessed(false)
{
}

Edge::Edge(const Edge &edge) :
    p1(edge.p1),
    p2(edge.p2),
    forbidden_point(edge.forbidden_point),
    IsProcessed(edge.IsProcessed)
{
}

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



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


struct Triangle {
    Edge edge12;
    Edge edge23;
    Edge edge31;
    Triangle(const Edge& edge, const Point& point);
    Triangle(const Edge& edge1, const Edge& edge2, const Edge& edge3);
    std::vector<Edge> GetEdges();
    Point GetExternalVector(const std::vector<Point>& points);
    std::vector<Point> GetPointsInProperOrder(const std::vector<Point> &points);
};

Triangle::Triangle(const Edge& edge, const Point& point) :
    edge12(edge, point),
    edge23(edge.p1, point, edge.p2),
    edge31(edge.p2, point, edge.p1)
{
}


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


Point GetOtherPoint(const std::vector<Point>& triangles_points, const std::vector<Point> &points) {
    if(triangles_points.size() < 3) {
        std::cerr<<" triangles_points.size() < 3 ";
        exit(1);
    }
    for (const auto& point: points) {
        if ((point != triangles_points[1] && point != triangles_points[2])
            && point != triangles_points[0]) {
            return point;
        }
    }
    std::cerr<<"NO OtherPoint for Triangles";
    exit(1);
}


std::vector<Point> GetPointsOfTriangle(const Triangle& triangle) {  //catch!!!
    std::vector<Point> points = { triangle.edge12.p1, triangle.edge12.p2, triangle.edge23.p1,
                                  triangle.edge23.p2, triangle.edge31.p1, triangle.edge31.p2 };
    std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2){ return p1.number <= p2.number  ; });
    auto last = std::unique(points.begin(), points.end());
    points.erase(last, points.end());
    return points;
}


Point Triangle::GetExternalVector(const std::vector<Point>& points) { //O(1)
    Triangle this_triangle = *this;
    std::vector<Point> triangles_points = GetPointsOfTriangle(this_triangle);

    if (triangles_points.size() < 3) {
        std::cerr<<" triangles_points.size() < 3 ";
        exit(1);
    }

    Point v1 = triangles_points[1] - triangles_points[0];
    Point v2 = triangles_points[2] - triangles_points[0];
    Point vector_normal_1 = VectorMultiplication(v1,v2);
    Point vector_normal_2 = VectorMultiplication(v2,v1);

    double D_1 = FindOutFaceD(vector_normal_1.x, vector_normal_1.y, vector_normal_1.z, triangles_points[0]);
    double D_2 = FindOutFaceD(vector_normal_2.x, vector_normal_2.y, vector_normal_2.z, triangles_points[0]);

    Point other_point = GetOtherPoint(triangles_points, points); // проверяем только на одной точке

    if (vector_normal_1*other_point + D_1 < 0) { //приколюшка только для грани!!!
        return vector_normal_1;
    }
    else if (vector_normal_2*other_point + D_2 < 0) {
        return vector_normal_2;
    }
    else {
        std::cout<<"Can't Find External Vector for Triangle";
        exit(1);
    }
}



std::vector<Point> Triangle::GetPointsInProperOrder(const std::vector<Point> &points) {
    Triangle this_triangle = *this;
    std::vector<Point> triangle_points = GetPointsOfTriangle(this_triangle);

    if (triangle_points.size() < 3) {
        std::cerr<<" triangles_points.size() < 3 ";
        exit(1);
    }

    std::vector<Point> proper_order_points;
    Point external_normal_vector = this->GetExternalVector(points);
    int iter_of_min = 0;                                                                            //FIX!!!
    for (int i = 1; i < triangle_points.size(); ++i) {
        if (triangle_points[iter_of_min].number > triangle_points[i].number) {
            iter_of_min = i;
        }
    }
    std::swap(triangle_points[iter_of_min],triangle_points[0]);
    proper_order_points.push_back(triangle_points[0]);

    Point v1 = VectorMultiplication(triangle_points[1] - triangle_points[0],external_normal_vector);
    Point v2 = VectorMultiplication(triangle_points[2] - triangle_points[0],external_normal_vector);
    double D_1 = FindOutFaceD(v1.x , v1.y, v1.z, triangle_points[1]);
    double D_2 = FindOutFaceD(v2.x , v2.y, v2.z, triangle_points[2]);
    if ( v1*triangle_points[2] + D_1 < 0 ) {
        proper_order_points.push_back(triangle_points[1]);
        proper_order_points.push_back(triangle_points[2]);
    }
    else if ( v2*triangle_points[1] + D_2 < 0 ) {
        proper_order_points.push_back(triangle_points[2]);
        proper_order_points.push_back(triangle_points[1]);
    }
    else {
        std::cout<<"Can't find right order";
        exit(1);
    }
    return proper_order_points;
}


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


bool IsFace(Triangle& triangle, const std::vector<Point>& points) { // how to do O(1)
    std::vector<Point> triangles_points = GetPointsOfTriangle(triangle);
    Point normal = triangle.GetExternalVector(points);

    double D_of_triangle = FindOutFaceD(normal.x, normal.y, normal.z, triangles_points[0]);
    std::vector<double> D_of_other_points;
    for (const 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 FindEdgeOnHull(const std::vector<Point>& points) {
    Point p1 = MostBottom(points);
    Point p2 = OtherPointFromSet(p1, points);
    for (const auto& point: points) {
        if ( p1 != point && OzAngle(p1,point) >= OzAngle(p1,p2) ) {
            p2 = point;
        }
    }
    return {p1,p2,p1};
}


Triangle FindtTriangleOnHull(std::vector<Point>& points) { //O(n^2)
    Edge edge = FindEdgeOnHull(points);
    Point pivot = edge.PivotAroundEdge(points);
    edge.forbidden_point = pivot;
    return  {edge, pivot};
}


Triangle FindNewTriangle(const std::vector<Point> &points, const Edge& edge) {

    Point p1 = edge.p1;
    Point p2 = edge.p2;
    Point p3 = edge.forbidden_point;
    std::vector<Point> triangle_points = {p1,p2,p3};

    Point rotate_vector (0,0,0);
    Point base_point (0,0,0);
    Point normal (0,0,0);

    Point p1p2 = p2 - p1;
    Point p2p1 = p1 - p2;
    Point norm_v1 = VectorMultiplication(p1p2,p3-p1);
    Point norm_v2 = VectorMultiplication(p2p1,p3-p2);
    Point other_point = GetOtherPoint(triangle_points, points);
    if (norm_v1*other_point + FindOutFaceD(norm_v1.x, norm_v1.y, norm_v1.z, p1) < 0) {
        rotate_vector = p1p2;
        base_point = p1;
        normal = norm_v1;
    }
    else if (norm_v2*other_point + FindOutFaceD(norm_v2.x, norm_v2.y, norm_v2.z, p1) < 0) {
        rotate_vector = p2p1;
        base_point = p2;
        normal = norm_v2;
    }
    else {
        std::cerr<<" Can't find rotate vector for ";
        edge.p1.Print();
        edge.p2.Print();
        exit(1);
    }

    Point pivot = other_point;
    Point current_vector = VectorMultiplication(pivot - base_point, rotate_vector);

    for (const auto& point: points) { // need O(n)
        if ((point != p1 && point != p2) && point != p3) {

            Point newvector = VectorMultiplication(point - base_point, rotate_vector);
            double newcos = (newvector * normal)/(newvector.GetModule() * normal.GetModule());
            double currentcos = (current_vector * normal)/(current_vector.GetModule() * normal.GetModule());

            if ( newcos > currentcos ) { // O(1)
                pivot = point;
            }
        }
    }
    return {edge, pivot};
}


Point Edge::PivotAroundEdge(const std::vector<Point> &points) { // O(n^2)
    Point p1 = this->p1;
    Point p2 = this->p2;
    for (const auto& point: points) {
        if ((point != p1 && point != p2)) {
            Edge this_edge = *this;
            Triangle triangle (this_edge, point);
            if (IsFace(triangle, points)) { // O(n)
                return point;
            }
        }
    }
}


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

template <class T>
bool IsIn(const T& myelement, std::vector<T>& elements) {
    for (int i = 0; i < elements.size(); ++i) {
        if (myelement == elements[i]) {
            elements[i].IsProcessed = true;
            return true;
        }
    }
    return  false;
}


void GiftWrapping(std::vector<Point>& points, std::vector<Triangle> & faces) {
    Triangle t = FindtTriangleOnHull(points); // O(n^2)
    faces.push_back(t);
    std::vector<Edge> edges = t.GetEdges();
    while (true) {
        Edge newedge = edges[0];
        bool flag = false;
        for (auto& edge: edges) {
            if (!edge.IsProcessed) {
                flag = true;
                edge.IsProcessed = true;
                newedge = edge;
                break;
            }
        }
        if (flag) {
            Triangle newtriangle = FindNewTriangle(points, newedge); //O(n)
            std::vector<Edge> triangles_edges = newtriangle.GetEdges();
            for (const auto& edge: triangles_edges) {
                if (!IsIn(edge, edges)) {                       //O(n)
                    edges.insert(edges.begin(), edge);
                }
            }
            faces.push_back(newtriangle);
        } else {
            break;
        }
    }
}


void SortByDigit(std::vector<std::vector<int>>& vector, int digit_number) {
    std::sort(vector.begin(), vector.end(),
              [digit_number](const std::vector<int>& a, const std::vector<int>&b) {
                  return a[digit_number] < b[digit_number];
              });
}


void Start() {

    std::vector<std::vector<std::vector<int>>> result;
    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;

        std::vector<std::vector<int>> lexic_order(faces.size());
        for (int k = 0; k < faces.size(); ++k) {
            lexic_order[k].push_back(3);
            for (auto point: faces[k].GetPointsInProperOrder(points)) {
                lexic_order[k].push_back(point.number);
            }
        }
        // sort
        for (int t = lexic_order[0].size() - 1; t > 0 ; --t) {
            SortByDigit(lexic_order, t);
        }

        result.push_back(lexic_order);

        // output
    }

    for (int l = 0; l < m; ++l) {
        std::cout<<result[l].size()<<std::endl;

        int fase_number = result[l].size();
        for (const auto& face: result[l]) {
            for (const auto& number: face) {
                std::cout<<number<<' ';
            }
            --fase_number;
            std::cout<<'\n';

        }
        if (fase_number != 0) {
            std::cout << '\n';
        }
    }
}


bool predicate(const Point& p1, const Point& p2) {
    return (p1 == p2);
}

int main() {

    Start();

    return  0;
}