#include "triangles.h"

#include <bits/stdc++.h>

using namespace std;

bool isInside(int a, int b, int c, int p) {
    int res = compare({Triangle(a, b, p), Triangle(a, c, p), Triangle(b, c, p)}, {Triangle(a, b, c)});
    return res == 0;
}

bool onOneSide(int a, int b, int p1, int p2) {
    int res = compare({Triangle(a, p1, p2), Triangle(b, p1, p2)}, {Triangle(a, b, p1), Triangle(a, b, p2)});
    return res != 0;
}

vector<vector<int>> anss;

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937 rng(52'52'239'67'67);

void solve2(int a, int b, int c, vector<int> pts) {
    // cout << ">>> " << a << ' ' << b << ' ' << c << '\n';
    vector<int> sAB, sBC, sAC;
    for(int i : pts) {
        if(!onOneSide(a, b, c, i)) { sAB.push_back(i); continue; }
        if(!onOneSide(b, c, a, i)) { sBC.push_back(i); continue; }
        if(!onOneSide(a, c, b, i)) { sAC.push_back(i); continue; }
    }
    anss.push_back({a, b, c});

    if(sAB.size() > 0) {
        int ii = sAB[rng() % sAB.size()];
        sAB.erase(find(sAB.begin(), sAB.end(), ii));
        solve2(a, b, ii, sAB);
    }
    if(sBC.size() > 0) {
        int ii = sBC[rng() % sBC.size()];
        sBC.erase(find(sBC.begin(), sBC.end(), ii));
        solve2(b, c, ii, sBC);
    }
    if(sAC.size() > 0) {
        int ii = sAC[rng() % sAC.size()];
        sAC.erase(find(sAC.begin(), sAC.end(), ii));
        solve2(a, c, ii, sAC);
    }
}

std::vector<std::vector<int>> solve(int n) {
    vector<int> pts(n);
    iota(pts.begin(), pts.end(), 0);
    shuffle(pts.begin(), pts.end(), rng);
    int aa = pts.back(); pts.pop_back();
    int bb = pts.back(); pts.pop_back();
    int cc = pts.back(); pts.pop_back();
    solve2(aa, bb, cc, pts);
    return anss;
}
