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

using namespace std;

#define sz(x) (int)x.size()

mt19937_64 rng(78620);

vector<vector<int>> fck(int ch0, int ch1, int ch2, vector<int> pp) {
    if (pp.empty()) {
        return {vector{ch0, ch1, ch2}};
    }
    int i = rng() % sz(pp);
    swap(pp[i], pp[0]);
    vector<int> p01, p12, p20;
    for (i = 1; i < sz(pp); ++i) {
        if (compare({Triangle(ch0, ch1, pp[0])},
            {Triangle(ch0, ch1, pp[i]), Triangle(ch1, pp[0], pp[i]), Triangle(pp[0], ch0, pp[i])}) == 0)
        {
            p01.emplace_back(i);
        }
        if (compare({Triangle(ch1, ch2, pp[0])},
            {Triangle(ch1, ch2, pp[i]), Triangle(ch2, pp[0], pp[i]), Triangle(pp[0], ch1, pp[i])}) == 0)
        {
            p12.emplace_back(i);
        }
        if (compare({Triangle(ch2, ch0, pp[0])},
            {Triangle(ch2, ch0, pp[i]), Triangle(ch0, pp[0], pp[i]), Triangle(pp[0], ch2, pp[i])}) == 0)
        {
            p20.emplace_back(i);
        }
    }
    auto res = fck(ch0, ch1, pp[0], p01);
    auto sub = fck(ch1, ch2, pp[0], p12);
    res.insert(res.end(), sub.begin(), sub.end());
    sub = fck(ch2, ch0, pp[0], p20);
    res.insert(res.end(), sub.begin(), sub.end());
    return res;
}

vector<vector<int>> solve(int n) {
    int ch0 = 2;
    for (int i = 3; i < n; ++i) {
        if (compare({Triangle(0, 1, ch0)}, {Triangle(0, 1, i)}) == -1) {
            ch0 = i;
        }
    }
    int ch1 = 1;
    for (int i = 2; i < n; ++i) {
        if (i != ch0 && compare({Triangle(0, ch0, ch1)}, {Triangle(0, ch0, i)}) == -1) {
            ch1 = i;
        }
    }
    int ch2 = 0;
    for (int i = 1; i < n; ++i) {
        if (i != ch0 && i != ch1 && compare({Triangle(ch0, ch1, ch2)}, {Triangle(ch0, ch1, i)}) == -1) {
            ch2 = i;
        }
    }
    return {{ch0, ch1, ch2}};
    vector<int> pp;
    pp.reserve(n - 3);
    for (int i = 0; i < n; ++i) {
        if (i != ch0 && i != ch1 && i != ch2) {
            pp.emplace_back(i);
        }
    }
    return fck(ch0, ch1, ch2, pp);
}