Stable

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

class ConvexHull {
public:
    explicit ConvexHull(size_t num) {
        dots.clear();
        num_dots = num;
    }
    ~ConvexHull() {
        dots.clear();
    }
    void read_dots(){
        for(int i = 0; i < num_dots; i++) {
            double x = 0;
            double y = 0;
            double z = 0;
            cin >> x >> y >> z;
            Point tmp(x, y, z);
            tmp.num = i;
            dots.push_back(tmp);
        }
    }
    void print_convex() {
        set<Flat>ans;

        Point First = dots[0];
        Point Second = dots[1];
        Point Third = dots[2];

        Initilize(First,Second, Third);

        queue<Flat> faces;


        Point vp = CrossProduct(Point(First, Second), Point(First, Third));
        Point n = CrossProduct(Point(First, Second), Point(First, Third));
        int someDot;
        for (int i = 0; i < 4; ++i) {
            if (First.num == i) {continue;}
            if (Second.num == i) {continue;}
            if (Third.num == i) {continue;}
            someDot = i;
            break;
        }
        if (Scalar(n, Point(First, dots[someDot])) > 0) {
            n.x = - n.x;
            n.y = - n.y;
            n.z = - n.z;
        }

        if (vp.x * n.x <= 0 && vp.y * n.y <= 0 && vp.z * n.z <= 0) {
            Point tmp = Second;
            Second = Third;
            Third = tmp;
        }

        Flat FirstFace = Flat(First, Second, Third,dots);

        faces.push(FirstFace);
        ans.insert(FirstFace);

        while(!faces.empty()) {
            Flat face = faces.front();
            Point n = face.Normal(dots);
            double g1 = -2, g2 = -2, g3 = -2;
            Flat f1, f2, f3;
            for (int i = 0 ; i < dots.size(); ++i) {
                if (face.First.num != i && face.Second.num != i && face.Third.num != i) {
                    Flat f1_test = Flat(face.First, dots[i], face.Second, dots);
                    Flat f2_test = Flat(face.Second, dots[i], face.Third, dots);
                    Flat f3_test = Flat(face.Third, dots[i], face.First, dots);
                    Point n1 = CrossProduct(Point(f1_test.First,f1_test.Second),Point(f1_test.First,f1_test.Third));
                    Point n2 = CrossProduct(Point(f2_test.First,f2_test.Second),Point(f2_test.First,f2_test.Third));
                    Point n3 = CrossProduct(Point(f3_test.First,f3_test.Second),Point(f3_test.First,f3_test.Third));
                    double new_g1 = Scalar(n, n1) / n.Mod() / n1.Mod();
                    double new_g2 = Scalar(n, n2) / n.Mod() / n2.Mod();
                    double new_g3 = Scalar(n, n3) / n.Mod() / n3.Mod();
                    if (new_g1 > g1) {
                        g1 = new_g1;
                        f1 = f1_test;
                    }
                    if (new_g2 > g2) {
                        g2 = new_g2;
                        f2 = f2_test;
                    }
                    if (new_g3 > g3) {
                        g3 = new_g3;
                        f3 = f3_test;
                    }
                }
            }
            bool b1 = true, b2 = true, b3 = true;
            if (ans.count(f1) != 0){b1 = false;}
            if (ans.count(f2) != 0){b2 = false;}
            if (ans.count(f3) != 0){b3 = false;}
            if (f1 == f2) {b1 = false;}
            if (f1 == f3) {b2 = false;}
            if (f2 == f3) {b3 = false;}
            if (b1) {
                faces.push(f1);
                ans.insert(f1);
            }
            if (b2) {
                faces.push(f2);
                ans.insert(f2);
            }
            if (b3) {
                faces.push(f3);
                ans.insert(f3);
            }
            faces.pop();
        }
        cout << ans.size() << endl;
        for (Flat face: ans) {
            cout << 3 << ' ' << face.First.num << ' ' << face.Second.num << ' ' << face.Third.num << endl;
        }
    }
private:
    const int MAX_COORDINATE = 1000000;
    struct Point{
        double x;   // Координата точки по x
        double y;   // Координата точки по y
        double z;   // Координата точки по z
        int num;    // Номер точки

        double Mod(){
            return sqrt(x*x+y*y+z*z);
        }
        Point() : x(0), y(0), z(0) {}
        Point(Point A, Point B) : x(B.x-A.x), y(B.y-A.y), z(B.z-A.z), num(-1) {}
        Point(double X, double Y, double Z) : x(X), y(Y), z(Z), num(-1) {}
    };
    Point static CrossProduct (const Point& A,const Point& B) {
        return Point{
                .x = A.y*B.z-A.z*B.y,
                .y = A.z*B.x-A.x*B.z,
                .z = A.x*B.y-A.y*B.x,
                };
    }
    double static Scalar(const Point& A,const Point& B) {
        return(A.x*B.x+A.y*B.y+A.z*B.z);
    }

    double FindAngleBetweenPlanes(Point F1, Point F2,Point F3, Point S1, Point S2,Point S3)
    {
        Point normalF = CrossProduct(Point(F1, F2), Point(F1, F3)); //������� � ��������� F.
        Point normalS = CrossProduct(Point(S1, S2), Point(S1, S3)); //������� � ��������� S.
        return Scalar(normalF, normalS) / normalF.Mod() / normalS.Mod();
    }

    vector<Point> dots;
    size_t num_dots;

    struct Flat {
        Point First;
        Point Second;
        Point Third;
        Flat() : First(), Second(), Third() {}
        Flat(Point F, Point S, Point T, vector<Point> dots) : First(F), Second(S), Third(T) {
            while (Second.num < First.num || Third.num < First.num) {
                Point tmp = First;
                First = Second;
                Second = Third;
                Third = tmp;
            }
        }
        Point Normal(vector<Point> dots) {
            Point n = CrossProduct(Point(First, Second), Point(First, Third));
            int someDot;
            for (int i = 0; i < 4; ++i) {
                if (First.num == i) {continue;}
                if (Second.num == i) {continue;}
                if (Third.num == i) {continue;}
                someDot = i;
                break;
            }
            if (Scalar(n, Point(First, dots[someDot])) > 0) {
                n.x = - n.x;
                n.y = - n.y;
                n.z = - n.z;
            }
            return n;
        }

        bool operator<(const Flat& other) const
        {
            return (First.num < other.First.num || (First.num == other.First.num && (Second.num < other.Second.num ||
                                                     Second.num == other.Second.num && Third.num < other.Third.num))) ? true : false;
        }

        bool operator==(const Flat& other) const
        {
            return (First.num == other.First.num & Second.num == other.Second.num && Third.num == other.Third.num) ? true : false;
        }
    };

    void Initilize(Point& First, Point& Second, Point& Third) {
        for (int i = 0; i < num_dots; i++) {  // Находим эту самую точку first_point
            if (dots[i].z < First.z) {
                First = dots[i];
            } else if (dots[i].z == First.z) {
                if (dots[i].x < First.x) {
                    First = dots[i];
                } else if (dots[i].x == First.x) {
                    if (dots[i].y < First.y) {
                        First = dots[i];
                    }
                }
            }
        }

        double maxAngle = -1;
        Point someDot = dots[First.num];
        Point someAnotherDot = dots[First.num];
        someDot.x -= 1;
        someAnotherDot.y -= 1;
        for (int i = 0; i < dots.size(); ++i) {
            if (i != First.num) {
                double angle = FindAngleBetweenPlanes(dots[First.num], someDot, someAnotherDot,  dots[First.num], someDot, dots[i]);
                    if (angle >= maxAngle) {
                        maxAngle = angle;
                        Second = dots[i];
                    }
                }
            }

        maxAngle = -2;
        for (int i = 0; i < dots.size(); ++i) {
            if (i != First.num && i != Second.num) {
                double angle = FindAngleBetweenPlanes(dots[First.num], someDot, Second,
                                                      dots[First.num], Second, dots[i]);
                if (angle >= maxAngle) {
                    maxAngle = angle;
                    Third = dots[i];
                }
            }
        }
    }
};

int main() {
    int num_tests = 0;
    cin >> num_tests;

    for(int test = 0; test < num_tests; test++){
        size_t num_dots = 0;
        cin >> num_dots;

        ConvexHull shell(num_dots);
        shell.read_dots();
        shell.print_convex();
    }
}