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

using namespace std;

bool check_in(Triangle t, int p) {
    vector<Triangle> left = {t};
    vector<Triangle> right = {{p, t.i, t.j}, {p, t.j, t.k}, {p, t.k, t.i}};
    int r = compare(left, right);
    return r == 0;
}


bool check_out(Triangle t, int p) {
    vector<Triangle> left = {{p, t.i, t.j}, {t.k, t.i, t.j}};
    vector<Triangle> right = {{p, t.j, t.k}, {p, t.k, t.i}};
    int r = compare(left, right);
    return r == 0;
}

bool dist_less(int x, pair<int, int> x1, int y, pair<int, int> y1) {
    vector<Triangle> left = {{x, x1.first, x1.second}};
    vector<Triangle> right = {{y, y1.first, y1.second}};
    if (x == x1.first || x == x1.second) return 1;
    if (y == y1.first || y == y1.second) return 0;
    int r = compare(left, right);
    return r == -1;
}

vector<vector<int>> ans;

mt19937 rng(8);

int find_mx_dist(vector<int>& v, pair<int, int> x) {
    int a = v[0];
    for (int i = 1; i < v.size(); i++) {
        if (dist_less(a, x, v[i], x)) {
            a = v[i];
        }
    }
    return a;
}

void solve_in_tr(vector<int> v, Triangle t) {
    assert(v.empty());
    if (v.empty()) {
        ans.push_back({t.i, t.j, t.k});
        return;
    }
    shuffle(v.begin(), v.end(), rng);
    int x = v[0];
    vector<int> ij, jk, ik;
    for (auto i : v) if (i != x) {
        if (check_in({t.i, t.j, x}, i)) {
            ij.push_back(i);
        } else if (check_in({t.j, t.k, x}, i)) {
            jk.push_back(i);
        } else {
            ik.push_back(i);
        }
    }
    solve_in_tr(ij, {t.i, t.j, x});
    solve_in_tr(jk, {t.j, t.k, x});
    solve_in_tr(ik, {t.i, t.k, x});
}

void solve_rec(vector<int> v) {
    if (v.size() <= 2) return;
    if (v.size() == 3) {
        ans.push_back(v);
        return;
    }
    shuffle(v.begin(), v.end(), rng);
    int a = find_mx_dist(v, {v[0], v[1]});
    int b = find_mx_dist(v, {a, v[1]});
    int c = find_mx_dist(v, {a, b});
    assert(a != b && b != c && c != a);
    vector<int> ins, ab{a, b}, bc{b, c}, ac{a, c};
    for (auto i : v) if (i != a && i != b && i != c) {
        if (check_in({a, b, c}, i)) {
            ins.push_back(i);
        } else if (check_out({a, b, c}, i)) {
            ab.push_back(i);
        } else if (check_out({a, c, b}, i)) {
            ac.push_back(i);
        } else {
            bc.push_back(i);
        }
    }
    solve_rec(ab);
    solve_rec(bc);
    solve_rec(ac);
    solve_in_tr(ins, {a, b, c});
}



vector<vector<int>> solve(int n) {
    ans.clear();
    vector<int> v(n);
    for (int i = 0; i < n; i++) v[i] = i;
    solve_rec(v);
    return ans;
}
