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

bool semiplane(int a, int b, int c, int d) {
    if (compare({Triangle(b, c, d)}, {Triangle(a, b, c), Triangle(a, c, d), Triangle(a, d, b)}) == 0) return 1;
    swap(a, b);
    if (compare({Triangle(b, c, d)}, {Triangle(a, b, c), Triangle(a, c, d), Triangle(a, d, b)}) == 0) return 1;
    swap(a, b);

    if (compare({Triangle(a, b, c), Triangle(a, b, d)}, {Triangle(a, c, d), Triangle(b, c, d)}) == 0) return 1;
    return 0;
}

vector <int> convex_hull(vector <int> points) {
    if (points.size() <= 3) return points;
    shuffle(points.begin(), points.end(), 0);

    int a = points[0], b = points[1];
    int pivot = points[2];

    vector <int> left, right;

    for (int i = 2; i < points.size(); i++) {
        int u = points[i];
        
        if (semiplane(u, pivot)) left.push_back(u);
        else right.push_back(u);
    }

    left = convex_hull(left);
    right = convex_hull(right);

    vector <int> ans, ans2;

    if (left.size()) {
        if (left.size() == 1) {
            ans.push_back(left[0]);
        } else {
            pivot = 0;
    
            for (int i = 0; i < left.size(); i++) {
                if (compare({Triangle(a, b, left[i])}, {Triangle(a, b, pivot)}) == -1) pivot = i;
            }
            
            int next = (pivot + 1) % left.size();
            int prev = (pivot + left.size() - 1) % left.size();

            if (semiplane(a, left[pivot], b, left[next])) {
                ans.push_back(left[pivot]);
                int bg = pivot;
                
                if (!semiplane(pivot, next, a, prev)) {
                    while ((pivot = (pivot + 1) % left.size()) != bg) ans.push_back(left[pivot]);
                } else {
                    while ((pivot = (pivot + left.size() - 1) % left.size()) != bg) ans.push_back(left[pivot]);
                }
            } else {
                ans.push_back(left[pivot]);
                int bg = pivot;
                
                if (!semiplane(pivot, next, a, prev)) {
                    while ((pivot = (pivot + 1) % left.size()) != bg) ans.push_back(left[pivot]);
                } else {
                    while ((pivot = (pivot + left.size() - 1) % left.size()) != bg) ans.push_back(left[pivot]);
                }

                reverse(ans.begin(), ans.end());
            }
        }
    }

    swap(left, right);
    swap(a, b);
    swap(ans, ans2);

    if (left.size()) {
        if (left.size() == 1) {
            ans.push_back(left[0]);
        } else {
            pivot = 0;
    
            for (int i = 0; i < left.size(); i++) {
                if (compare({Triangle(a, b, left[i])}, {Triangle(a, b, pivot)}) == -1) pivot = i;
            }
            
            int next = (pivot + 1) % left.size();
            int prev = (pivot + left.size() - 1) % left.size();

            if (semiplane(a, left[pivot], b, left[next])) {
                ans.push_back(left[pivot]);
                int bg = pivot;
                
                if (!semiplane(pivot, next, a, prev)) {
                    while ((pivot = (pivot + 1) % left.size()) != bg) ans.push_back(left[pivot]);
                } else {
                    while ((pivot = (pivot + left.size() - 1) % left.size()) != bg) ans.push_back(left[pivot]);
                }
            } else {
                ans.push_back(left[pivot]);
                int bg = pivot;
                
                if (!semiplane(pivot, next, a, prev)) {
                    while ((pivot = (pivot + 1) % left.size()) != bg) ans.push_back(left[pivot]);
                } else {
                    while ((pivot = (pivot + left.size() - 1) % left.size()) != bg) ans.push_back(left[pivot]);
                }

                reverse(ans.begin(), ans.end());
            }
        }
    }

    swap(left, right);
    swap(a, b);
    swap(ans, ans2);

    ans.push_back(a);

    for (int x : ans2) ans.push_back(x);
    ans.push_back(b);

    return ans;
}

vector <vector <int>> solve(int n) {
    vector <int> points(n);
    iota(points.begin(), points.end(), 0);

    vector <int> ch = convex_hull(points);

    vector <vector <int>> ans;

    for (int i = 2; i < ch.size(); i++) {
        ans.push_back({ch[0], ch[1], ch[i]});
    }

    return ans;
}
