#include "triangles.h"
#include <vector>
#include <numeric>
#include <random>

using namespace std;

struct TriangleData {
    int a, b, c;
    bool active;
};

struct EdgeData {
    int a, b, inner;
    int prev, next;
    bool active;
};

struct Loc {
    int type;
    int id;
};

bool point_in_triangle(int pt, int a, int b, int c) {
    return compare({Triangle(a, b, c)}, {Triangle(a, b, pt), Triangle(b, c, pt), Triangle(c, a, pt)}) == 0;
}

bool cross_edge(int a, int b, int c, int pt) {
    return compare({Triangle(a, c, pt), Triangle(b, c, pt)}, {Triangle(a, b, c), Triangle(a, b, pt)}) == 0;
}

bool sees_edge(int a, int b, int inner, int pt) {
    if (cross_edge(a, b, inner, pt)) return true;
    if (point_in_triangle(a, b, inner, pt)) return true;
    if (point_in_triangle(b, a, inner, pt)) return true;
    return false;
}

vector<vector<int> > solve(int n) {
    vector<int> P(n);
    iota(P.begin(), P.end(), 0);
    mt19937 rng(1337);
    for (int i = n - 1; i > 0; --i) {
        int j = rng() % (i + 1);
        swap(P[i], P[j]);
    }

    vector<TriangleData> triangles;
    vector<EdgeData> edges;
    vector<Loc> loc(n);
    triangles.push_back({P[0], P[1], P[2], true});
    edges.push_back({P[0], P[1], P[2], 2, 1, true});
    edges.push_back({P[1], P[2], P[0], 0, 2, true});
    edges.push_back({P[2], P[0], P[1], 1, 0, true});

    for (int i = 3; i < n; i++) {
        int q = P[i];
        if (point_in_triangle(q, P[0], P[1], P[2])) loc[q] = {0, 0};
        else if (sees_edge(P[0], P[1], P[2], q)) loc[q] = {1, 0};
        else if (sees_edge(P[1], P[2], P[0], q)) loc[q] = {1, 1};
        else loc[q] = {1, 2};
    }

    for (int i = 3; i < n; i++) {
        int p = P[i];
        if (loc[p].type == 0) {
            int t_id = loc[p].id;
            int a = triangles[t_id].a;
            int b = triangles[t_id].b;
            int c = triangles[t_id].c;
            triangles[t_id].active = false;
            int t1 = triangles.size();
            triangles.push_back({a, b, p, true});
            int t2 = triangles.size();
            triangles.push_back({b, c, p, true});
            int t3 = triangles.size();
            triangles.push_back({c, a, p, true});
            for (int j = i + 1; j < n; j++) {
                int q = P[j];
                if (loc[q].type == 0 && loc[q].id == t_id) {
                    if (point_in_triangle(q, a, b, p)) loc[q] = {0, t1};
                    else if (point_in_triangle(q, b, c, p)) loc[q] = {0, t2};
                    else loc[q] = {0, t3};
                }
            }
        } else {
            int e_id = loc[p].id;
            int curr = e_id;
            while (true) {
                int prev = edges[curr].prev;
                if (sees_edge(edges[prev].a, edges[prev].b, edges[prev].inner, p)) {
                    curr = prev;
                    if (curr == e_id) break;
                } else break;
            }
            int first_e = curr;
            curr = e_id;
            while (true) {
                int next = edges[curr].next;
                if (sees_edge(edges[next].a, edges[next].b, edges[next].inner, p)) {
                    curr = next;
                    if (curr == e_id) break;
                } else break;
            }
            int last_e = curr;

            vector<int> vis;
            curr = first_e;
            while (true) {
                vis.push_back(curr);
                if (curr == last_e) break;
                curr = edges[curr].next;
            }

            int k = vis.size();
            vector<int> V(k + 1);
            for (int j = 0; j < k; j++) {
                V[j] = edges[vis[j]].a;
            }
            V[k] = edges[vis[k - 1]].b;

            int t_start = triangles.size();
            for (int j = 0; j < k; j++) {
                triangles.push_back({V[j], V[j + 1], p, true});
            }

            int e_left = edges.size();
            edges.push_back({V[0], p, V[1], edges[first_e].prev, -1, true});

            int e_right = edges.size();
            edges.push_back({p, V[k], V[k - 1], e_left, edges[last_e].next, true});

            edges[e_left].next = e_right;
            edges[edges[first_e].prev].next = e_left;
            edges[edges[last_e].next].prev = e_right;

            for (int id: vis) edges[id].active = false;

            for (int j = i + 1; j < n; j++) {
                int q = P[j];
                if (loc[q].type == 1) {
                    bool in_vis = false;
                    for (int id: vis) {
                        if (loc[q].id == id) {
                            in_vis = true;
                            break;
                        }
                    }
                    if (in_vis) {
                        bool assigned = false;
                        for (int m = 0; m < k; m++) {
                            if (point_in_triangle(q, V[m], V[m + 1], p)) {
                                loc[q] = {0, t_start + m};
                                assigned = true;
                                break;
                            }
                        }
                        if (!assigned) {
                            if (sees_edge(V[0], p, V[1], q)) {
                                loc[q] = {1, e_left};
                                assigned = true;
                            }
                        }
                        if (!assigned) {
                            if (sees_edge(p, V[k], V[k - 1], q)) {
                                loc[q] = {1, e_right};
                                assigned = true;
                            }
                        }
                        if (!assigned) {
                            for (int e = 0; e < (int) edges.size(); e++) {
                                if (edges[e].active && sees_edge(edges[e].a, edges[e].b, edges[e].inner, q)) {
                                    loc[q] = {1, e};
                                    assigned = true;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    vector<vector<int> > ans;
    for (const auto &t: triangles) {
        if (t.active) {
            ans.push_back({t.a, t.b, t.c});
        }
    }
    return ans;
}
