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

using namespace std;

mt19937 rnd(228);

vector <vector <int>> ans;

void get(vector <int> &ind) {
    if (ind.size() < 3) {
        return;
    }
    shuffle(ind.begin(), ind.end(), rnd);

    int n = ind.size();

    int a = ind[0];
    int b = ind[1];
    int c = ind[2];
    ans.push_back({a, b, c});

    Triangle t(a, b, c);
    // cout << a << " " << b << " " << c << '\n';

    vector <int> hui_ab;
    vector <int> hui_ac;
    vector <int> hui_bc;

    // cout << n << " f" << '\n';

    for (int i = 3; i < n; i ++) {
        Triangle t_ab(a, b, ind[i]);
        Triangle t_ac(a, c, ind[i]);
        Triangle t_bc(b, c, ind[i]);

        int f1 = compare({t, t_ac}, {t_ab, t_bc});
        if (f1 == 0) {
            hui_ac.push_back(ind[i]);
            continue;
        }

        int f2 = compare({t, t_ab}, {t_ac, t_bc});
        if (f2 == 0) {
            hui_ab.push_back(ind[i]);
            continue;
        }

        hui_bc.push_back(ind[i]);
    }

    hui_ab.push_back(a);
    hui_ab.push_back(b);

    hui_bc.push_back(b);
    hui_bc.push_back(c);

    hui_ac.push_back(a);
    hui_ac.push_back(c);

    // for (auto x : hui_ab) {
    //     cout << x << " ";
    // }
    // cout << "ab" << '\n';
    //
    // for (auto x : hui_ac) {
    //     cout << x << " ";
    // }
    // cout << "ac" << '\n';
    //
    // for (auto x : hui_bc) {
    //     cout << x << " ";
    // }
    // cout << "bc" << '\n';

    get(hui_ab);
    get(hui_ac);
    get(hui_bc);
}

bool check(int a, int b, int c, int x) {
    Triangle t(a, b, c);
    Triangle t1(a, b, x);
    Triangle t2(a, c, x);
    Triangle t3(b, c, x);

    int f = compare({t}, {t1, t2, t3});
    if (f == 0) {
        return true;
    }
    return false;
}

bool check(vector <int> &ind, int x) {
    int a = ind[0];
    int n = ind.size();
    for (int i = 1; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            int b = ind[i];
            int c = ind[j];
            if (check(a, b, c, x)) {
                return true;
            }
        }
    }
    return false;
}

std::vector<std::vector<int>> solve(int n) {
    vector <int> ind(n);
    for (int i = 0; i < n; i ++) {
        ind[i] = i;
    }

    shuffle(ind.begin(), ind.end(), rnd);

    vector <int> tek = {ind[0], ind[1], ind[2]};
    for (int i = 3; i < n; i ++) {
        if (check(tek, ind[i])) {
            continue;
        }
        vector <int> tek2 = {ind[i]};
        tek.push_back(ind[i]);
        for (auto j : tek) {
            if (j == ind[i]) {
                continue;
            }
            if (check(tek, j)) {
                continue;
            }
            tek2.push_back(j);
        }
        tek = tek2;
    }

    get(tek);

    return ans;
}
