#include "triangles.h"
#include<bits/stdc++.h>

std::mt19937 rng(23423);

using tri = std::array<int, 3>;

Triangle conv(tri t) {
    return Triangle(t[0], t[1], t[2]);
}

bool checkin(tri t, int k) {
    return compare({conv(t)}, {Triangle(t[0], t[1], k), Triangle(t[0], t[2], k), Triangle(t[1], t[2], k)}) == 0;
}

// void solve_triangle(tri, std::vector<int>);
// void solve_line(int, int, std::vector<int>);

std::vector<std::vector<int>> ans;

void dividenconquer(tri t, std::vector<int> vec) {
    std::vector<int> abc;
    for (auto x : vec) {
        if (x == t[0] || x == t[1] || x == t[2]) continue;
        abc.push_back(x);
    }
    if (abc.size()) {
        int k = abc[rng() % abc.size()];
        std::vector<int> aob, aoc, boc;
        for (auto x : abc) {
            if (x == k) continue;
            if (checkin({t[0], t[1], k}, x)) aob.push_back(x);
            else if (checkin({t[0], t[2], k}, x)) aoc.push_back(x);
            else boc.push_back(x);
        }
        dividenconquer({t[0], t[1], k}, aob);
        dividenconquer({t[0], t[2], k}, aoc);
        dividenconquer({t[1], t[2], k}, boc);
    } else {
        ans.push_back({t[0], t[1], t[2]});
    }
}
void solve(std::vector<int> vec) {
    if (vec.size() < 3) return;
    tri t{vec[0], vec[1], vec[2]};
    for (int i = 3; i < vec.size(); ++i) {
        tri nw = t;
        for (int j = 0; j < 3; ++j) {
            for (int k = j + 1; k < 3; ++k) {
                tri c{t[j], t[k], vec[i]};
                if (compare({conv(c)}, {conv(nw)}) == 1) nw = c;
            }
        }
    }
    std::vector<int> abc, ab = {t[0], t[1]}, ac = {t[0], t[2]}, bc = {t[1], t[2]};
    for (auto x : vec) {
        if (x == t[0] || x == t[1] || x == t[2]) continue;
        Triangle ABC(t[0], t[1], t[2]);
        Triangle ABX(t[0], t[1], x);
        Triangle AXC(t[0], x, t[2]);
        Triangle XBC(x, t[1], t[2]);
        if (compare({ABC}, {ABX, AXC, XBC}) == 0) abc.push_back(x);
        else if (compare({AXC, XBC}, {ABC, ABX}) == 0) ab.push_back(x);
        else if (compare({ABX, AXC}, {ABC, XBC}) == 0) bc.push_back(x);
        else ac.push_back(x);
    }
    dividenconquer(t, abc);
    solve(ab);
    solve(ac);
    solve(bc);
}
// void solve_triangle(tri t, std::vector<int> vec) {
//     std::vector<int> abc, ab, ac, bc;
//     for (auto x : vec) {
//         if (x == t[0] || x == t[1] || x == t[2]) continue;
//         Triangle ABC(t[0], t[1], t[2]);
//         Triangle ABX(t[0], t[1], x);
//         Triangle AXC(t[0], x, t[2]);
//         Triangle XBC(x, t[1], t[2]);
//         if (compare({ABC}, {ABX, AXC, XBC}) == 0) abc.push_back(x);
//         else if (compare({AXC, XBC}, {ABC, ABX}) == 0) ab.push_back(x);
//         else if (compare({ABX, AXC}, {ABC, XBC}) == 0) bc.push_back(x);
//         else ac.push_back(x);
//     }
//     dividenconquer(t, abc);
//     solve_line(t[0], t[1], ab);
//     solve_line(t[0], t[2], ac);
//     solve_line(t[1], t[2], bc);
// }
// void solve_line(int a, int b, std::vector<int> vec) {
//     int k = -1;
//     for (auto x : vec) {
//         if (x == a || x == b) continue;
//         if (k == -1 || compare({Triangle(a, b, x)}, {Triangle(a, b, k)}) == 1) k = x; 
//     }
//     if (k != -1) {
//         solve_triangle({a, b, k}, vec);
//     }
// }

std::vector<std::vector<int>> solve(int n) {
    ans.clear();
    // tri t = {0, 1, 2};
    // for (int i = 3; i < n; ++i) {
    //     tri nw = t;
    //     for (int j = 0; j < 3; ++j) {
    //         for (int k = j + 1; k < 3; ++k) {
    //             tri c{t[j], t[k], i};
    //             if (compare({conv(c)}, {conv(nw)}) == 1) nw = c;
    //         }
    //     }
    //     t = nw; 
    // }
    std::vector<int> vec(n);
    std::iota(vec.begin(), vec.end(), 0);
    solve(vec);
    // solve_triangle(t, vec);
    return ans;
}