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


int f(int a, int b, int c, int i){
    int x = compare({{a, b, c}, {b, c, i}}, {{a, b, i}, {a, c, i}});
    int y = compare({{a, b, c}, {c, a, i}}, {{b, c, i}, {b, a, i}});
    int z = compare({{a, b, c}, {a, b, i}}, {{c, a, i}, {c, b, i}});
    if(x == 0) return 1;
    if(y == 0) return 2;
    if(z == 0) return 3;
    if(x > 0 && y > 0 && z > 0) return 0;
    if(x > 0) return -1;
    if(y > 0) return -2;
    if(z > 0) return -3;
    cout << "ERROR" << endl;
    return 0;
}

bool inside(int a, int b, int c, int i){
    return compare({{a, b, c}}, {{i, b, c}, {a, i, c}, {a, b, i}}) == 0;
}

bool same_side(int a, int b, int i, int j){
    int t = f(a, b, i, j);
    return t == 0 || t == 1 || t == 2 || t == -3;
}

vector<int> add_p(vector<int> &a, int i, int l, int r){
    int m = a.size();
    vector<int> b = {i};
    for(int j = l; j != r; j = (j + 1)%m){
        b.push_back(a[j]);
    }
    b.push_back(a[r]);
    return b;
}

bool edge_type(vector<int> &a, int i, int x){
    int m = a.size();
    return same_side(a[x], a[(x + 1)%m], a[(x + 2)%m], i);
}

int furthest(int a, int b, int n){
    int j = -1;
    for(int i = 0; i < n; ++i){
        if(i != a && i != b){
            if(j == -1) j = i;
            else{
                if(compare({{a, b, i}}, {{a, b, j}}) > 0){
                    j = i;
                }
            }
        }
    }
    return j;
}

vector<vector<int>> solve(int n) {
    vector<int> a;
    int x = 0, y = 1, z = furthest(0, 1, n);
    x = furthest(y, z, n);
    y = furthest(x, z, n);
    a = {x, y, z};
    // for(int i = 3; i < n; ++i){
    //     int m = a.size(), l, r;
    //     if(same_side(i, a[0], a[1], a[m - 1])){
    //         cout << i << a[0] << a[1] << a[m - 1] << endl;
    //         l = 0;
    //         int x = 0, y = m - 1;
    //         int xt = edge_type(a, i, x), yt = edge_type(a, i, y);
    //         while(x + 1 < y){
    //             int z = (x + y)/2;
    //             int zt = edge_type(a, i, z);
    //             if(zt == xt){
    //                 x = z;
    //             }
    //             else y = z;
    //         }
    //         r = y;
    //     }
    //     else{
    //         int ll = 1, rr = m - 1;
    //         while(ll + 1 < rr){
    //             int mm = (ll + rr)/2;
    //             if(same_side(i, a[0], a[1], a[mm])) ll = mm;
    //             else rr = mm;
    //         }
    //         int x = 0, y = ll;
    //         int xt = edge_type(a, i, x), yt = edge_type(a, i, y);
    //         while(x + 1 < y){
    //             int z = (x + y)/2;
    //             int zt = edge_type(a, i, z);
    //             if(zt == xt){
    //                 x = z;
    //             }
    //             else y = z;
    //         }
    //         l = y;
    //         if(!same_side(a[l], i, a[(l + m - 1)%m], a[(l + 1)%m])){
    //             continue;
    //         }
    //         x = ll, y = m - 1;
    //         swap(xt, yt);
    //         while(x + 1 < y){
    //             int z = (x + y)/2;
    //             int zt = edge_type(a, i, z);
    //             if(zt == xt){
    //                 x = z;
    //             }
    //             else y = z;
    //         }
    //         r = y;
    //     }
    //     if(!edge_type(a, i, l)) swap(l, r);
    //     cout << endl;
    //     print(a);
    //     cout << l << ' ' << r << endl << endl;
    //     a = add_p(a, i, l, r);
    // }
    // return {a};
    vector<bool> b(n);
    for(int x : a) b[x] = 1;
    vector<vector<int>> ans;
    for(int i = 1; i < a.size() - 1; ++i){
        ans.push_back({a[0], a[i], a[i + 1]});
    }
    for(int i = 0; i < n; ++i) if(!b[i]){
        for(auto &v : ans){
            int x = v[0], y = v[1], z = v[2];
            if(inside(x, y, z, i)){
                v[0] = i;
                ans.push_back({x, i, z});
                ans.push_back({x, y, i});
                break;
            }
        }
    }
    return ans;
}
