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

std::vector<std::vector<int>> solve(int n) {
    vector<int> v = {0, 1, 2};
    for (int i = 3; i < n; ++i) {
        int i1 = 0, i2 = 1, i3 = 2, i4 = 3;
        vector<vector<int>> vv = {v, {v[0], v[1], i}, {v[0], v[2], i}, {v[1], v[2], i}};
        vector<Triangle> nw1 = {Triangle(v[0], v[1], i)};
        vector<Triangle> nw2 = {Triangle(v[0], v[2], i)};
        vector<Triangle> nw3 = {Triangle(v[1], v[2], i)};
        vector<Triangle> nw4 = {Triangle(v[1], v[2], v[0])};
        if (compare(nw1, nw2) == -1) {
            nw1 = nw2;
            swap(i1, i2);
        }
        if (compare(nw3, nw4) == -1) {
            nw3 = nw4;
            swap(i3, i4);
        }
        if (compare(nw1, nw3) == -1) {
            swap(i1, i3);
        }
        v = vv[i1];
    }
    return {v};
}
