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

using namespace std;
mt19937 rnd(1908);/*
struct Triangle {
	int i, j, k;

	Triangle() = default;
	Triangle(int i_, int j_, int k_) : i(i_), j(j_), k(k_) {}
};

int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);*/
vector<vector<int>> solve(int n) {
	vector<int> p(n);
	for (int i = 0; i < n; ++i) {
		p[i] = i;
	}
	shuffle(p.begin(), p.end(), rnd);
	Triangle now(p[0], p[1], p[2]);
	for (int i = 3; i < n; ++i) {
		if (compare({ now }, { Triangle(now.i, now.j, p[i]) }) == -1) {
			now.k = p[i];
		}
		else if (compare({ now }, { Triangle(now.i,  p[i], now.k) }) == -1) {
			now.j = p[i];
		}
		else if (compare({ now }, { Triangle(p[i], now.j, now.k) }) == -1) {
			now.j = p[i];
		}
	}
	shuffle(p.begin(), p.end(), rnd);
	for (int i = 0; i < n; ++i) {
		if (p[i] != now.i && p[i] != now.i && p[i] != now.k) {
			if (compare({ now }, { Triangle(now.i, now.j, p[i]) }) == -1) {
				now.k = p[i];
			}
			else if (compare({ now }, { Triangle(now.i,  p[i], now.k) }) == -1) {
				now.j = p[i];
			}
			else if (compare({ now }, { Triangle(p[i], now.j, now.k) }) == -1) {
				now.j = p[i];
			}
		}
	}
	shuffle(p.begin(), p.end(), rnd);
	for (int i = 0; i < n; ++i) {
		if (p[i] != now.i && p[i] != now.i && p[i] != now.k) {
			if (compare({ now }, { Triangle(now.i, now.j, p[i]) }) == -1) {
				now.k = p[i];
			}
			else if (compare({ now }, { Triangle(now.i,  p[i], now.k) }) == -1) {
				now.j = p[i];
			}
			else if (compare({ now }, { Triangle(p[i], now.j, now.k) }) == -1) {
				now.j = p[i];
			}
		}
	}
	return { {now.i, now.j, now.k} };
	/*for (int i = 0; i < 24; ++i) {
		if (!compare({ Triangle(p[0], p[1], p[2]) }, { Triangle(p[0], p[1], p[3]), Triangle(p[0], p[2], p[3]), Triangle(p[1], p[2], p[3]) })) {
			return { {p[3], p[0], p[1]} , {p[3], p[2], p[1]} , {p[3], p[0], p[2]} };
		}
		next_permutation(p.begin(), p.end());
	}
	for (int i = 0; i < 24; ++i) {
		if (!compare({ Triangle(p[0], p[1], p[2]) ,  Triangle(p[0], p[2], p[3]) }, { Triangle(p[0], p[1], p[3]), Triangle(p[1], p[2], p[3]) })) {
			return { {p[0], p[1], p[2]}, {p[0], p[2], p[3]} };
		}
		next_permutation(p.begin(), p.end());
	}*/
}