#include "triangles.h"
#include <bits/stdc++.h>

using namespace std;

bool compare_triangles(const Triangle& a, const Triangle& b) {
    auto res = compare({a}, {b});
    return (res < 0);
}

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

vector<int> solve_with_convex_hull(int first, int second, const vector<int>& order) {
    if (order.empty()) {
        return {second};
    }

    vector<int> left;
    left.emplace_back(first);
    vector<int> right;
    right.emplace_back(second);
    for (int i : order) {
        while (left.size() >= 2 && !check_intersection(left[(int)left.size() - 2], i, left.back(), second)) {
            left.pop_back();
        }
        left.emplace_back(i);
        while (right.size() >= 2 && !check_intersection(right[(int)right.size() - 2], i, first, right.back())) {
            right.pop_back();
        }
        right.emplace_back(i);
    }

    vector<int> res = right;
    for (int i = (int)left.size() - 2; i >= 1; i--) {
        res.emplace_back(left[i]);
    }

    return res;
}

vector<vector<int>> solve(int n) {
    int first = 2;
    for (int i = 3; i < n; i++) {
        if (compare_triangles(Triangle(0, 1, first), Triangle(0, 1, i))) {
            first = i;
        }
    }
    int second = (first + 2) % n;
    for (int i = 3; i < n; i++) {
        if (compare_triangles(Triangle(first, (first + 1) % n, second), Triangle(first, (first + 1) % n, (first + i) % n))) {
            second = (first + i) % n;
        }
    }

    vector<int> order;
    order.reserve(n - 2);
    for (int i = 0; i < n; i++) {
        if (i == first || i == second) {
            continue;
        }
        int l = -1;
        int r = (int)order.size();
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (compare_triangles(Triangle(first, second, order[mid]), Triangle(first, second, i))) {
                l = mid;
            } else {
                r = mid;
            }
        }
        order.emplace_back(i);
        for (int j = (int)order.size() - 2; j >= r; j--) {
            swap(order[j], order[j + 1]);
        }
    }

    vector<int> down, up;
    for (int i : order) {
        if (i == order.back()) {
            up.emplace_back(i);
        } else if (check_intersection(first, second, i, order.back())) {
            down.emplace_back(i);
        } else {
            up.emplace_back(i);
        }
    }

    auto res1 = solve_with_convex_hull(first, second, down);
    auto res2 = solve_with_convex_hull(second, first, up);
    for (const auto& t : res2) {
        res1.emplace_back(t);
    }
    return {res1};
}
