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


using ll = int;
mt19937 rnd(42);
bool inside(ll x, ll a, ll b, ll c) {
    Triangle fi(x, a, b);
    Triangle se(x, c, b);
    Triangle th(x, a, c);
    Triangle mn(a, b, c);
    return compare({fi, se, th}, {mn}) == 0;
}

bool diag(ll a, ll b, ll c, ll d) {
    Triangle fi(a, b, d);
    Triangle se(a, b, c);
    Triangle th(c, d, a);
    Triangle fo(c, d, b);
    return compare({fi, se}, {th, fo}) == 0;
}
void shuff(vector<int>& v) {
    for (int i = 0; i < v.size(); ++i) {
        swap(v[i], v[rnd() % (i + 1)]);
    }
}
vector<vector<int>> solve(int n) {
    vector<int> v;
    for (ll i = 0; i < n; ++i) {
        v.push_back(i);
    }
    while (v.size() != 3) {
        shuff(v);
        int a= v[0], b = v[1], c = v[2];
        vector<int> tod;
        for (int i = 4; i < v.size(); ++i) {
            if (inside(v[i], a, b, c)) tod.push_back(v[i]);
        }
        for (int& i : tod) {
            v.erase(find(v.begin(), v.end(), i));
        }
    }
    return {{v[0], v[1], v[2]}};
}