Fivt_3/task-B/24.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* parent_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) const;
};


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


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


template <class Triangle>
Point Edge<Triangle>::GetForbiddenPoint() const {
    for (auto point: parent_triangle->GetPoints()) {
        if (point != p1 && point != p2) {
            return  point;
        }
    }
    std::cout<<"Not ForbiddenPoint for Edge";
    exit(1);
}


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


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

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


Point Triangle::GetExternalVector(const std::vector<Point>& points) const {
    const std::vector<Point> triangles_points = this->GetPoints();
    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 = this->GetOtherPoint(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::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;
}



struct {
    bool operator()(const Point& a, const Point& b) const
    {
        return a.number < b.number;
    }
} ComparePointByNumber;
std::vector<Point> Triangle::PointsInProperOrder(const std::vector<Point>& points) const {
    std::vector<Point> triangle_points = this->GetPoints();
    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>> Triangle::GetEdges() const{
    std::vector<Edge<Triangle>> edges = {edge12,edge23,edge31};
    return edges;
}

Point Triangle::GetOtherPoint(const std::vector<Point> &points) const {
    const std::vector<Point> triangles_points = this->GetPoints();
    for (auto point: points) {
        if ((point != triangles_points[1] && point != triangles_points[2])
            && point != triangles_points[0]) {
            return point;
        }
    }
    std::cout<<"No other points for triangle";
    exit(1);
}


bool IsFace(const Triangle& triangle, const std::vector<Point>& points) { // O(n)
    const std::vector<Point> triangles_points = triangle.GetPoints();
    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 (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);
    Triangle triangle(edge, pivot);
    triangle.edge12.parent_triangle = &triangle;
    return  triangle;
}



// вернет такую точку, что получилась грань
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(const std::vector<Edge<Triangle>>& 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);
    faces.push_back(t);
    std::vector<Edge<Triangle>> edges = t.GetEdges();
    while (IsNotUsedEdges(edges)) { // O(n)
        Edge<Triangle>& newedge = edges.back();
        if (!newedge.IsProcessed) {
            Point pivot = newedge.PivotAroundEdge(points, newedge.GetForbiddenPoint());
            Triangle newtriangle (newedge, pivot); //O(n)
            for (Edge<Triangle> triangles_edge: newtriangle.GetEdges()) {
                if (!IsIn(triangles_edge, edges)) {
                    edges.push_back(triangles_edge);
                }
            }
            faces.push_back(newtriangle);
        }
    }

}

int main() {

//  Point p1 (1,0,0,0);
//  Point p2 (0,1,0,1);
//  Point p3 (0,0,1,2);
//  Point p4 (0,0,0,3);
//
//  std::vector<Point> points = {p1,p2,p3,p4};
//  std::vector<Triangle> faces;
//
//  GiftWrapping(points, faces);

    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.PointsInProperOrder(points)) {
                std::cout<<point.number<<' ';
            }
            std::cout<<'\n';
        }
    }


    return  0;
}