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

mt19937 rng(42);

bool between(int x, int a, int b, int c){
    auto Triangle1 = Triangle(a, b, c);
    auto t1 = Triangle(x, b, c), t2 = Triangle(a, x, c), t3 = Triangle(a, b, x);
    return (compare({Triangle1}, {t1, t2, t3}) == 0);
}

bool cross(int a, int b, int c, int d){
    auto tri1 = Triangle(a, b, c), tri2 = Triangle(a, b, d);
    auto Tri1 = Triangle(a, c, d), Tri2 = Triangle(c, b, d);
    return (compare({tri1, tri2}, {Tri1, Tri2}) == 0);

}

int nl;

vector<int> merge_sort(vector<int> a){
    if(a.size() <= 2){
        return a;
    }
    int x = rng() % (a.size() - 1) + 1;
    int y = x;
    x = a[x];
    vector<int> b1, b2;
    b1.push_back(a[0]);
    for(int i = 1; i < a.size(); i++){
        if(i == y){
            continue;
        }
        if(cross(nl, x, a[0], a[i])){
            b2.push_back(a[i]);
        }else{
            b1.push_back(a[i]);
        }
    }
    b1 = merge_sort(b1);
    b2 = merge_sort(b2);
    if(b1.size() > 1 && cross(nl, b1[0], b1[b1.size() - 1], x)){
        reverse(b1.begin(), b1.end());
    }
    if(b2.size() > 1 && cross(nl, b2[b2.size() - 1], b2[0], x)){
        reverse(b2.begin(), b2.end());
    }
    b1.push_back(x);
    for(auto u: b2){
        b1.push_back(u);
    }
    return b1;
}

vector<vector<int>> solve(int n){
    vector<int> srt;
    for(int i = 0; i < n; i++){
        int _ = 1000;
        while(_--){
            int x1 = rng() % n;
            int x2 = rng() % n;
            int x3 = rng() % n;
            set<int> m = {i, x1, x2, x3};
            if(m.size() < 4 || !between(i, x1, x2, x3)){
                continue;
            }else{
                break;
            }
        }
        if(_ > 0){
            srt.push_back(i);
        }
    }
    nl = srt[srt.size() - 1];
    srt.pop_back();
    vector<int> r1 = merge_sort(srt);
    vector<vector<int>> r;
    for(int i = 0; i < n - 2; i++){
        r.push_back({nl, r1[i], r1[i + 1]});
    }
    return r;
}
