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

vector<int> perm;
mt19937 rnd;

int ask(vector<Triangle> l, vector<Triangle> r) {
    for (Triangle& t : l) {
        t.i = perm[t.i];
        t.j = perm[t.j];
        t.k = perm[t.k];
    }
    for (Triangle& t : r) {
        t.i = perm[t.i];
        t.j = perm[t.j];
        t.k = perm[t.k];
    }
    return compare(l, r);
}

bool inside(int p, int a, int b, int c) {
    return ask({{a, b, c}}, {{p, a, b}, {p, b, c}, {p, c, a}}) == 0;
}

bool intersect(int a, int b, int c, int d) {
    return ask({{a, b, c}, {a, b, d}}, {{b, c, d}, {a, c, d}}) == 0;
}

int cmp(const Triangle& a, const Triangle& b) {
    return ask({a}, {b});
}

int find_furthest(int a, int b, int n) {
    int res = -1;
    for (int i = 0; i < n; ++i) {
        if (i == a || i == b) continue;
        if (res == -1 || cmp({a, b, i}, {a, b, res}) == 1) {
            res = i;
        }
    }
    return res;
}

vector<vector<int>> ans;

vector<vector<int>> out(vector<vector<int>> ans) {
    for (auto& elem : ans) {
        for (int& x : elem) {
            x = perm[x];
        }
    }
    return ans;
}

std::vector<std::vector<int>> solve(int n) {
    perm.resize(n);
    iota(perm.begin(), perm.end(), 0);
    shuffle(perm.begin(), perm.end(), rnd);

    int x = find_furthest(0, 1, n);
    int y = find_furthest(x, (x + 1) % n, n);
    int z = find_furthest(x, y, n);

    /// x, y, z on the convex hull
    vector<int> full_hull;
        full_hull = {x, y, z};
    ans.push_back(full_hull);
    return out(ans);
}
