#include "triangles.h"
#include <algorithm>
#include <vector>
#include <random>
#include <cmath>

std::mt19937_64 rnd(42);

std::uniform_real_distribution gen;

std::vector<std::vector<int>> solve(int n) {
    std::vector<int> p;
    for (int i = 1; i < n; ++i) p.push_back(i);
    std::shuffle(p.begin(), p.end(), rnd);

    for (int t = 0; t < 1'000'00; ++t) {
        int i = std::uniform_int_distribution(1, (int) p.size() - 1)(rnd);

        if (compare({{0, p[i], p[i - 1]}, {0, p[i], p[i + 1]}}, {{0, p[i - 1], p[i + 1]}, {0, p[i + 1], p[i]}}) == 1) {
            std::swap(p[i], p[i + 1]);
        }

        if (compare({{0, p[i], p[i - 1]}, {0, p[i], p[i + 1]}}, {{0, p[i - 1], p[i + 1]}, {0, p[i - 1], p[i]}}) == 1) {
            std::swap(p[i], p[i - 1]);
        }

    }

    std::vector<std::vector<int>> ans;
    for (int i = 0; i + 1 < p.size(); ++i) {
        ans.push_back({0, p[i], p[i + 1]});
    }
    return ans;
}
