#include "triangles.h"
#include<bits/stdc++.h>
std::vector<std::vector<int>> solve2(int n, std::vector<int>&pt) {
    if (n <= 2) {
        return {};
    }
    std::vector<std::vector<int>>ans = {{pt[0], pt[1], pt[2]}};
    std::vector<int>part1 = {pt[0], pt[1]}, part2 = {pt[1], pt[2]}, part3 = {pt[0], pt[2]};
    for (int i = 3; i < n; i++) {
        std::vector<Triangle>left = {Triangle(pt[0], pt[1], pt[i]), Triangle(pt[0], pt[1], pt[2])};
        std::vector<Triangle>right = {Triangle(pt[2], pt[0], pt[i]), Triangle(pt[1], pt[2], pt[i])};
        if (compare(left, right) == 0) {
            part1.push_back(pt[i]);
        }
    }
    for (int i = 3; i < n; i++) {
        std::vector<Triangle>left = {Triangle(pt[1], pt[2], pt[i]), Triangle(pt[0], pt[1], pt[2])};
        std::vector<Triangle>right = {Triangle(pt[0], pt[1], pt[i]), Triangle(pt[0], pt[2], pt[i])};
        if (compare(left, right) == 0) {
            part2.push_back(pt[i]);
        }
    }
    for (int i = 3; i < n; i++) {
        std::vector<Triangle>left = {Triangle(pt[0], pt[2], pt[i]), Triangle(pt[0], pt[1], pt[2])};
        std::vector<Triangle>right = {Triangle(pt[2], pt[1], pt[i]), Triangle(pt[1], pt[0], pt[i])};
        if (compare(left, right) == 0) {
            part3.push_back(pt[i]);
        }
    }
    std::vector<std::vector<int>>t, rt;
    t = solve2(part1.size(), part1);
    for (auto i: t) {
        rt.push_back(i);
    }
    t = solve2(part2.size(), part1);
    for (auto i: t) {
        rt.push_back(i);
    }
    t = solve2(part3.size(), part1);
    for (auto i: t) {
        rt.push_back(i);
    }
    return rt;
}

std::vector<std::vector<int>> solve(int n) {
    std::vector<int>a(n);
    iota(a.begin(), a.end(), 0);
    return solve2(n, a);
}
