#include "triangles.h"

#include <bits/stdc++.h>

#include <random>

using namespace std;

int cnt = (int) 1e6 * 2;


int compar(vector<Triangle> left, vector<Triangle> right) {
    cnt--;
    if (cnt < 0) exit(-1);
    return compare(left, right);
}

bool inside(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    left.emplace_back(b, c, i);
    right.emplace_back(a, b, c);
    return compar(left, right) == 0;
}

bool check(int a, int b, int c, int i) {
    vector<Triangle> left, right;
    left.emplace_back(a, b, i);
    left.emplace_back(a, c, i);
    right.emplace_back(a, b, c);
    right.emplace_back(b, c, i);
    return compar(left, right) == 0;
}

vector<vector<int> > ans;

void solve(vector<int> points, vector<int> tr) {
    if (points.empty()) {
        ans.emplace_back(tr);
        return;
    }
    int A = tr[0], B = tr[1], C = points[0];
    for (int i: points) {
        if (i == C) continue;
        vector<Triangle> left, right;
        left.emplace_back(A, B, i), right.emplace_back(A, B, C);
        if (compar(left, right) == -1)
            C = i;
    }
    vector<int> C01, C02, C12;
    for (int i: points) {
        if (i == C) continue;
        if (inside(tr[0], tr[1], C, i))
            C01.emplace_back(i);
        else if (inside(tr[1], tr[2], C, i))
            C12.emplace_back(i);
        else
            C02.emplace_back(i);
    }
    solve(C01, vector<int>{tr[0], tr[1], C});
    solve(C02, vector<int>{tr[0], tr[2], C});
    solve(C12, vector<int>{tr[1], tr[2], C});
}

mt19937 rnd(INT_MAX);

void solve(vector<int> p, int s = -1, int t = -1) {
    if ((int) p.size() == 2)
        return;
    if ((int) p.size() == 3) {
        ans.emplace_back(vector<int>{p[0], p[1], p[2]});
        return;
    }
    vector<int> bigger = {p[0], p[1], p[2]};
    if (s != -1) {
        bigger = {s, t};
        vector<int> x;
        for (int i: p) if (i != s && i != t) x.emplace_back(i);
        bigger.emplace_back(x[rnd() % (int) x.size()]);
    } else {
        int f1 = rnd() % (int) p.size();
        int f2 = f1;
        while (f1 == f2) f2 = rnd() % (int) p.size();
        int f3 = f2;
        while (f1 == f3 || f2 == f3) f3 = rnd() % (int) p.size();
        bigger = {p[f1], p[f2], p[f3]};
    }
    vector<int> tri = bigger, p1, p2, p3, in;
    for (int i: p) {
        if (i == tri[0]) {
            p1.emplace_back(i), p3.emplace_back(i);
        } else if (i == tri[1]) {
            p1.emplace_back(i), p2.emplace_back(i);
        } else if (i == tri[2]) {
            p2.emplace_back(i), p3.emplace_back(i);
        } else {
            if (inside(tri[0], tri[1], tri[2], i)) {
                in.emplace_back(i);
                continue;
            }
            if (s == -1) {
                if (check(tri[0], tri[1], tri[2], i))
                    p2.emplace_back(i);
                else if (check(tri[1], tri[2], tri[0], i))
                    p3.emplace_back(i);
                else
                    p1.emplace_back(i);
            } else {
                if (check(tri[0], tri[1], tri[2], i))
                    p2.emplace_back(i);
                else
                    p3.emplace_back(i);
            }
        }
    }
    solve(in, tri);
    solve(p1, tri[0], tri[1]), solve(p2, tri[1], tri[2]), solve(p3, tri[2], tri[0]);
}

std::vector<std::vector<int> > solve(int n) {
    ans.clear();
    vector<int> p;
    for (int i = 0; i < n; i++) p.emplace_back(i);
    // shuffle(p.begin(), p.end(), std::mt19937(std::random_device()()));
    solve(p);
    return ans;
}
