#include <bits/stdc++.h>
#include "triangles.h"
using namespace std;

using ll = int;

ll farthest(ll v, ll u, ll n) {
    auto mx_tr = Triangle();
    ll res = -1;
    for (ll i = 0; i < n; i++) {
        if (i == v || i == u)
            continue;
        if (res == -1) {
            mx_tr = Triangle(v, u, i);
            res = i;
            continue;
        }
        auto cur = Triangle(v, u, i);
        ll comp = compare({mx_tr}, {cur});
        if (comp == -1) {
            mx_tr = cur;
            res = i;
        }
    }

    return res;
}

bool inside(ll v, Triangle big_tr) {
    auto [u1, u2, u3] = big_tr;
    vector<Triangle> trs;
    trs.push_back(Triangle(u1, u2, v));
    trs.push_back(Triangle(u1, u3, v));
    trs.push_back(Triangle(u2, u3, v));
    ll comp = compare({big_tr}, trs);
    if (comp == 0)
        return true;
    return false;
}

vector<vector<ll>> g;
vector<ll> ans_vs;

void dfs(ll v) {
    if (g[v].empty()) {
        ans_vs.push_back(v);
        return;
    }
    for (ll u : g[v]) {
        dfs(u);
    }
}

vector<vector<int>> solve(int n) {
    int v = farthest(0, 1, n);
    int u = -1;
    if (v != 0)
        u = farthest(0, v, n);
    else
        u = farthest(1, v, n);
    int w = farthest(v, u, n);

    vector<Triangle> vs = {Triangle(v, u, w)};
    g.assign(1, {});
    vector<bool> used(n, false);
    used[v] = used[u] = used[w] = true;
    for (ll i = 0; i < n; i++) {
        if (used[i])
            continue;
        ll cur = 0;
        while (true) {
            if (g[cur].empty())
                break;
            ll nxt = g[cur][2];
            for (ll j = 0; j < 2; j++) {
                if (inside(i, vs[g[cur][j]])) {
                    nxt = g[cur][j];
                    break;
                }
            }
            cur = nxt;
        }

        auto [u1, u2, u3] = vs[cur];
        g[cur].push_back(vs.size());
        vs.push_back(Triangle(u1, u2, i));
        g.push_back({});
        g[cur].push_back(vs.size());
        vs.push_back(Triangle(u1, u3, i));
        g.push_back({});
        g[cur].push_back(vs.size());
        vs.push_back(Triangle(u2, u3, i));
        g.push_back({});
    }

    dfs(0);

    vector<vector<ll>> ans;
    for (ll cv : ans_vs) {
        ans.push_back({vs[cv].i, vs[cv].j, vs[cv].k});
    }

    return ans;
}