// ConsoleApplication3.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "triangles.h"

using namespace std;
using ll = long long;

// checks that d is in triangle a,b,c
bool check(int a, int b, int c, int d)
{
	Triangle t = { a,b,c };
	Triangle x = { d,a,b };
	Triangle y = { d,b,c };
	Triangle z = { d,a,c };
	if (compare({ t }, { x,y,z }) == 0)
		return true;
	return false;
}

// -1: a < b
// 0 a = b
// 1 : a > b
int cmp(Triangle a, Triangle b)
{
	return compare({ a }, { b });
}

int cmp(vector<Triangle> a, vector<Triangle> b)
{
	return compare(a, b);
}

vector <int> normal(Triangle t)
{
	return { t.i,t.j,t.k };
}

vector <vector <int>> normal(vector<Triangle> t)
{
	vector <vector<int>> res;
	for (auto& i : t)
	{
		res.push_back(normal(i));
	}
	return res;
}

using answer_t = vector <vector <int>>;

void run(int a, int b, int c, vector <int> inp, answer_t& ans)
{
	if (inp.empty())
	{
		ans.push_back({ a,b,c });
		return;
	}
	int d = inp.back();
	inp.pop_back();
	vector <int> x, y, z;
	for (auto& i : inp)
	{
		if (check(a, b, d, i))
			x.push_back(i);
		else if (check(a, c, d, i))
			y.push_back(i);
		else if (check(b, c, d, i))
			z.push_back(i);
	}
	run(a, b, d, x, ans);
	run(a, c, d, y, ans);
	run(b, c, d, z, ans);
}

int qr = 0;
void on_query()
{
	qr++;
	if (qr >= 1'000'000)
		exit(-1);
}
bool inside(const vector <int>& poly, int pt)
{
	int a = poly[0];
	for (size_t i = 1; i + 1 < poly.size(); i++)
	{
		int b = poly[i];
		int c = poly[i + 1];
		on_query();
		if (check(a, b, c, pt))
			return true;
	}
	return false;
}

void rebound(vector <int>& poly)
{
	for (int i = 0; i < poly.size(); i++)
	{
		auto pol = poly;
		pol.erase(pol.begin() + i);
		if (inside(pol, poly[i]))
		{
			poly.erase(poly.begin() + i);
			i--;
		}
	}
}

answer_t solve(int n)
{
	/*assert(n == 4);
	auto create = [&](int x, int y, int z)
	{
		int t = 6 - x - y - z;
		vector <vector<int>> lst;
		lst.push_back({ x,y,t });
		lst.push_back({ x,z,t });
		lst.push_back({ y,z,t });
		return lst;
	};
	if (check(0, 1, 2, 3))
		return create(0, 1, 2);
	if (check(0, 1, 3, 2))
		return create(0, 1, 3);
	if (check(0, 2, 3, 1))
		return create(0, 2, 3);
	if (check(1, 2, 3, 0))
		return create(1, 2, 3);
	vector< vector<Triangle>> vars;
	auto diam = [&](int x, int y)
	{
		int z = (x == 0 || y == 0 ? (x == 1 || y == 1 ? 2 : 1) : 0);
		int t = 6 - x - y - z;
		if (compare({ {x,y,z},{x,y,t} }, { { z,t,x },{z,t,y} }) == 0)
		{
			vars.push_back({ {x,y,z},{x,y,t} });
		}
	};
	diam(0, 1);
	diam(0, 2);
	diam(0, 3);
	sort(vars.begin(), vars.end(), [](auto x, auto y) {return cmp(x, y) < 0; });
	return normal(vars.back());*/
	vector <int> polygon = { 0,1,2 };
	for (size_t i = 3; i < n; i++)
	{
		if (inside(polygon, i))
			continue;
		polygon.push_back(i);
		rebound(polygon);
	}
	// int a = polygon[0], b = polygon[1], c = polygon[2];
	answer_t ans;
	//run(a, b, c, bad, ans);
	ans.push_back(polygon);
	return ans;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
