#include<bits/stdc++.h>

#include "triangles.h"

using namespace std;

int in(int a, int b, int c, int o) {
    int y = compare({Triangle(a, b, c)}, {Triangle(a, b, o), Triangle(b, c, o), Triangle(a, c, o)});
    if (y == 0) return 1;
    return 0;
}

int dif(int a, int b, int p, int o) {
    int y = compare({Triangle(a, b, o), Triangle(a, b, p)}, {Triangle(o, p, a), Triangle(o, p, b)});
    if (y == 0) return 1;
    return 0;
}

mt19937 rnd(57);

vector<vector<int>> solve(int n) {
    vector<int> now = {(int)rnd() % n, (int)rnd() % n, (int)rnd() % n};
    for (int i = 0; i < n; ++i) {
        if (i == now[0] || i == now[1] || i == now[2]) continue;
        if (in(now[0], now[1], i, now[2])) {
            now[2] = i;
        } else if (in(now[0], now[2], i, now[1])) {
            now[1] = i;
        } else if (in(now[1], now[2], i, now[0])) {
            now[0] = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i == now[0] || i == now[1] || i == now[2]) continue;
        if (in(now[0], now[1], i, now[2])) {
            now[2] = i;
        } else if (in(now[0], now[2], i, now[1])) {
            now[1] = i;
        } else if (in(now[1], now[2], i, now[0])) {
            now[0] = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i == now[0] || i == now[1] || i == now[2]) continue;
        if (in(now[0], now[1], i, now[2])) {
            now[2] = i;
        } else if (in(now[0], now[2], i, now[1])) {
            now[1] = i;
        } else if (in(now[1], now[2], i, now[0])) {
            now[0] = i;
        }
    }
    vector<int> ch(n);
    ch[now[0]] = 1;
    ch[now[1]] = 1;
    ch[now[2]] = 1;
    vector<vector<int>> all;
    all.push_back(now);
    return all;
    for (int i = 0; i < n; ++i) {
        if (ch[i]) continue;
        ch[i] = 1;
        int fl = -1;
        for (int u = 0; u < (int)all.size(); ++u) {
            auto val = all[u];
            if (in(val[0], val[1], val[2], i)) {
                all.push_back({val[0], val[1], i});
                all.push_back({val[0], val[2], i});
                all.push_back({val[1], val[2], i});
                fl = u;
                break;
            }
        }
        assert(fl != -1);
        if (fl != -1) all.erase(all.begin() + fl);
    }
    return all;
}
