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

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rnd() % (r - l + 1);
}


bool inside(int i, int j, int k, int dot) {
    vector<Triangle> left = {Triangle(i, j, k)};
    vector<Triangle> right = {
        Triangle(dot, i, j),
        Triangle(dot, i, k),
        Triangle(dot, j, k)
    };
    int res = compare(left, right);
    return res == 0;
}

std::vector<std::vector<int> > solve(int n) {
    std::vector<std::vector<int> > ans;

    int ops = 1.5e6;
    set<array<int, 3> > used;
    while (ops > 0) {
        vector<int> cur;
        while (cur.size() < 3) {
            int v = rand(0, n - 1);
            bool flag = false;
            for (auto val: cur) {
                flag |= val == v;
            }
            if (flag) {
                continue;
            }
            cur.emplace_back(v);
        }
        for (int i = 0; i < n && ops > 0; i++) {
            if (i == cur[0] || i == cur[1] || i == cur[2]) {
                continue;
            }
            ops--;
            if (inside(cur[0], cur[1], cur[2], i)) {
                int ind = rand(0, 2);
                swap(cur[ind], i);
            }
        }
        if (ops != 0) {
            if (cur[0] > cur[1]) {
                swap(cur[0], cur[1]);
            }
            if (cur[1] > cur[2]) {
                swap(cur[1], cur[2]);
            }
            if (cur[0] > cur[1]) {
                swap(cur[0], cur[1]);
            }
            if (!used.contains({cur[0], cur[1], cur[2]})) {
                used.insert({cur[0], cur[1], cur[2]});
                ans.push_back({cur[0], cur[1], cur[2]});
            }
        }
    }
    return ans;
    vector<int> hull = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        bool in = false;
        for (int j = 1; j < hull.size() && !in; j++) {
            for (int k = j + 1; k < hull.size() && !in; k++) {
                in |= inside(hull[0], hull[j], hull[k], i);
            }
        }
    }
    /*
    Triangle cur = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        if (inside(cur.i, cur.j, cur.k, i)) {
            continue;
        }
        Triangle v2 = {cur.i, cur.j, i};
        Triangle v3 = {cur.j, cur.k, i};
        Triangle v4 = {cur.i, cur.k, i};
        for (auto v: {v2, v3, v4}) {
            vector<Triangle> left = {cur};
            vector<Triangle> right = {v};
            if (compare(left, right) == -1) {
                cur = v;
            }
        }
    }
    ans = {{cur.i, cur.j, cur.k}};
    return ans;
    */
    for (int mid = 0; mid < n; mid++) {
        vector<int> nemid;
        for (int j = 0; j < n; j++) {
            if (j == mid) {
                continue;
            }
            nemid.emplace_back(j);
        }
        if (inside(nemid[0], nemid[1], nemid[2], mid)) {
            ans.push_back({nemid[0], nemid[1], mid});
            ans.push_back({nemid[1], nemid[2], mid});
            ans.push_back({nemid[0], nemid[2], mid});
            return ans;
        }
    }

    // иначе четырехугольник
    vector<Triangle> norm = {Triangle(0, 1, 2), Triangle(0, 1, 3)};
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            vector<int> ost;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) {
                    continue;
                }
                ost.emplace_back(k);
            }
            vector<Triangle> left = {Triangle(i, j, ost[0]), Triangle(i, j, ost[1])};
            vector<Triangle> right = {Triangle(ost[0], ost[1], i), Triangle(ost[0], ost[1], j)};
            if (compare(left, right) == 0) {
                norm = left;
                ans.emplace_back();
                auto &v = ans[0];
                v.push_back(norm[0].i);
                v.push_back(norm[0].k);
                v.push_back(norm[0].j);
                v.push_back(6 - v[0] - v[1] - v[2]);
                return ans;
            }
        }
    }


    return ans;
}
