#include "triangles.h"
#include<bits/stdc++.h>
bool in(std::vector<int>pt) {
    int n = 4;
    std::vector<Triangle>left = {Triangle(pt[1], pt[2], pt[3])};
    std::vector<Triangle>right = {{Triangle(pt[0], pt[1], pt[2])},
                                  {Triangle(pt[0], pt[1], pt[3])},
                                  {Triangle(pt[0], pt[2], pt[3])}};
    return compare(left, right) == 0;
}

bool ask(int a, int b, int c, int d) {
    std::vector<Triangle>left = {Triangle(a, b, c), Triangle(a, b, d)};
    std::vector<Triangle>right = {Triangle(b, d, c), Triangle(a, c, d)};
    return compare(left, right) == 0;
}

std::vector<std::vector<int>> solve(int n) {
    std::vector<int>pt = {0, 1, 2}, pt2;
    int sz = 3;
    int fl = 1;
    for (int i = 3; i < n; i++) {
        std::vector<int>stay(sz, 1);
        fl = 1;
        for (int j = 2; j < sz; j++) {
            if (in({i, pt[0], pt[1], pt[j]})) {
                fl = 0;
                continue;
            }
        }
        if (fl == 0) {
            continue;
        }
        fl = 1;
        for (int j = 0; j < sz; j++) {
            if (stay[j] == 0 || stay[(j + 1)%sz] == 0) {
                continue;
            }
            for (int g = 0; g < sz; g++) {
                if (stay[g] == 0 || g == j || (j + 1) % sz == g) {
                    continue;
                }
                if (in({pt[g], i, pt[j], pt[(j + 1)%sz]})) {
                    fl = 0;
                    stay[g] = 0;
                }
            }
        }
        if (fl == 0) {
            pt2 = {i};
            int ind_st = 0;
            while (stay[ind_st]) {
                ind_st++;
            }
            for (int j = (ind_st + 1)%sz; j != ind_st; j = (j + 1)%sz) {
                if (stay[j]) {
                    pt2.push_back(pt[j]);
                }
            }
            pt = pt2;
            sz = pt.size();
        } else {
            pt2 = {};
            int ind = 0;
            for (int j = 0; j < sz; j++) {
                pt2.push_back(j);
                if (j == 0) {
                    ind = sz - 1;
                } else if (j == sz - 1) {
                    ind = 1;
                } else {
                    ind = 0;
                }
                if (ask(pt[j], pt[(j + 1)%sz], ind, i)) {
                    pt2.push_back(i);
                }
            }
            pt = pt2;
            sz = pt.size();
        }
    }
    return {pt};
}