#pragma GCC optimize("Ofast", "unroll-loops")
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <array>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <random>

#include "triangles.h"

#define rep(n) for (int (i) = 0; (i) < (n); (i)++)
#define all(n) (n).begin(), (n).end()
#define rall(n) (n).rbegin(), (n).rend()
#define mp make_pair
#define ll long long
#define ld long double
//#define int long long
//#define FILE
//#define DEBUG



using namespace std;

bool is_in(int num, int p1, int p2, int p3) {
    vector<Triangle> left, right;
    vector<int> A{p1, p2, p3};
    left = {{A[0], A[1], num}, {A[0], A[2], num}, {A[1], A[2], num}};
    right = {{A[0], A[1], A[2]}};
    int res = compare(left, right);
    return res == 0;
}

bool is_dif_side(int p1, int p2, int pl, int pr) {
    if (is_in(p1, pl, p2, pr) || is_in(p2, pl, p1, pr))
        return true;

    vector<Triangle> left, right;
    left = {{p1, p2, pl}, {p1, p2, pr}};
    right = {{pl, pr, p1}, {pl, pr, p2}};
    int res = compare(left, right);

    return res == 0;
}

int find_line(vector<int> P, int p) {
    int sz = P.size();
    for (int cur = 0; cur < sz; cur++) {
        int nxt = (cur + 1) % sz;
        int other = (nxt + 1) % sz;
        if (is_dif_side(P[cur], P[nxt], p, P[other]))
            return cur;
    }
    return -1;
}

vector<vector<int>> solve(int n) {
    vector<int> P;
    for (int p = 0; p < n; p++) {
        if (P.size() <= 2) {
            P.push_back(p);
            continue;
        }
        int cur = find_line(P, p);
        if (cur == -1)
            continue;
        int nxt = (cur + 1) % P.size();
        int prv = (cur - 1 + P.size()) % P.size();
        if (is_in(P[cur], P[prv], p, P[nxt])) {
            P.erase(P.begin() + cur);
            p--;
            continue;
        }
        cur++;
        nxt = (cur + 1) % P.size();
        prv = (cur - 1 + P.size()) % P.size();
        if (is_in(P[cur], P[prv], p, P[nxt])) {
            P.erase(P.begin() + cur);
            p--;
            continue;
        }
        P.insert(P.begin() + cur, p);
    }
    return {P};
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
#ifdef FILE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "W", stdout);
#endif
#ifndef DEBUG
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve(4);
    }
#else

#endif
}