#include "triangles.h"

#include <algorithm>

#define PB push_back
#define X first
#define Y second

typedef std::pair <int , int> pii;



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


std::vector <int> findbig(int n)
{
    int a = 0 , b = 1 , c = 2;

    bool lamp = true;
    while (lamp == true)
    {
        lamp = false;

        for (int i = 0; i < n; i++)
        {
            if (i == a || i == b || i == c)
                continue;

            if (compare({Triangle(a , b , c)} , {Triangle(a , b , i)}) < 0)
            {
                c = i;
                lamp = true;
            }
        }

        for (int i = 0; i < n; i++)
        {
            if (i == a || i == b || i == c)
                continue;

            if (compare({Triangle(a , b , c)} , {Triangle(a , i , c)}) < 0)
            {
                b = i;
                lamp = true;
            }
        }

        for (int i = 0; i < n; i++)
        {
            if (i == a || i == b || i == c)
                continue;

            if (compare({Triangle(a , b , c)} , {Triangle(i , b , c)}) < 0)
            {
                a = i;
                lamp = true;
            }
        }
    }

    return {a , b , c};
}


int a , b , c;
bool cmp(int x , int y)
{
    return compare({Triangle(a , b , x)} , {Triangle(a , b , y)}) > 0;
}

std::vector<std::vector<int>> solve(int n)
{
    std::vector <int> big = findbig(n);
    a = big[0];
    b = big[1];
    c = big[2];

    std::vector <int> inside;
    for (int i = 0; i < n; i++)
        if (i != a && i != b && i != c)
            inside.PB(i);

    std::sort(inside.begin() , inside.end() , cmp);

    std::vector <std::pair <int , pii>> tr;
    tr.PB({a , {b , c}});

    for (auto& e : inside)
    {
        int curr = -1;
        for (int i = tr.size() - 1; i >= 0; i--)
            if (ins(tr[i].X , tr[i].Y.X , tr[i].Y.Y , e))
            {
                curr = i;
                break;
            }

        auto save = tr[curr];
        tr.erase(tr.begin() + curr);

        tr.PB({save.X , {save.Y.X , e}});
        tr.PB({save.X , {save.Y.Y , e}});
        tr.PB({save.Y.X , {save.Y.Y , e}});
    }

    std::vector <std::vector <int>> ans;
    for (auto& e : tr)
        ans.PB({e.X , e.Y.X , e.Y.Y});

    return ans;
}
