\begin{problem}{Разрезание торта}{стандартный ввод}{стандартный вывод}{2 секунды}{512 мегабайт}
 
\textbf{Данную задачу можно решать только на языке программирования C++.}

Организаторы Закрытой олимпиады школьников по программированию решили заказать большой торт на вечерний банкет. Для этого они заказали торт с $n$ свечками, пронумерованными от $0$ до $n-1$. Известно, что свечки находятся в различных точках на плоскости, никакие три свечки не лежат на одной прямой, никакие четыре свечки не образуют трапецию (четырехугольник с двумя параллельными сторонами).

Чтобы всем достался кусочек торта, организаторы хотят заранее построить способ разрезать торт на максимальное число кусочков. К сожалению, вам неизвестно расположение свечек на торте, а единственный доступный способ узнать, как выглядит торт --- переписка с кондитерской по электронной почте.

В одном сообщении вы можете попросить взвесить не более четырех треугольных кусочков, с вершинами в свечках:

\begin{itemize}
\item Вы предоставляете два списка треугольников \texttt{left} и \texttt{right}, суммарно содержащих не более четырех треугольников. Треугольники могут пересекаться, содержать общие свечки и даже совпадать.
\item В кондитерской вырежут треугольные кусочки в соответствии с запрошенными списками из нескольких копий торта и положат кусочки из \texttt{left} на левую чашу весов, кусочки из \texttt{right} на правую чашу весов.
\item Вам отправят результат взвешивания. Будем считать, что вес кусочка равен его площади. В результате вы узнаете, в каком из списков треугольников суммарная площадь больше, или что площади совпадают.
\end{itemize}

После нескольких взвешиваний вы должны найти способ разрезать торт. Каждый кусочек должен быть выпуклым многоугольником с вершинами в свечках. Вершины кусочка должны быть перечислены в порядке обхода по или против часовой стрелки. Любые два кусочка не должны пересекаться по внутренним точкам. Вы должны вернуть список кусочков, суммарная площадь которых максимально возможная. Также в некоторых группах требуется максимизировать число кусочков.

\SolutionFormat

Это необычная задача. Она имеет формат тестирования с грейдером, где вам необходимо реализовать только функцию \texttt{solve} с решением. Эта функция будет вызвана тестирующей программой жюри (грейдером), и возвращаемое значение функции будет принято как решение задачи.

В частности, это означает, что в отправленном вами коде \textbf{не должно быть ввода или вывода}. Ваш код \textbf{не должен} содержать функцию \texttt{main}. При необходимости вы можете реализовать произвольное количество вспомогательных функций, структур, классов и глобальных переменных, но весь код вашего решения должен находиться в одном файле.

Вы должны реализовать следующую функцию:

\begin{verbatim}
std::vector<std::vector<int>> solve(int n);
\end{verbatim}

Функция \texttt{solve} принимает на вход единственное число $n$~--- количество свечек.

В реализации функции \texttt{solve} вы можете использовать функцию \texttt{compare}, которую реализует грейдер:

\begin{verbatim}
int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);
\end{verbatim}

Данная функция принимает на вход два непустых списка треугольников суммарного размера не более $4$. В качестве результата она возвращает $-1$, если суммарная площадь треугольников в \texttt{left} меньше суммарной площади треугольников в \texttt{right}, $0$, если площади равны и $1$, иначе. Если сделать некорректный запрос или исчерпать лимит на количество запросов, то программа автоматически завершит свою работу.

Для того, чтобы получить доступ к функции \texttt{compare} в решении, первой строчкой вашего кода нужно подключить заголовочный файл следующей строчкой:

\begin{verbatim}
#include "triangles.h"
\end{verbatim}

В этом же файле определена используемая в функции \t{compare} структура \t{Triangle}:

\begin{verbatim}
struct Triangle {
    int i, j, k;

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

Данная структура описывает один треугольный кусочек, параметры \t{i}, \t{j} и \t{k} описывают номера свечек, образующих вершины треугольного кусочка. Номера свечек должны быть различными для одного треугольного кусочка, но могут повторяться в нескольких треугольниках.

\textbf{В код отправляемого решения вам не надо включать определение структуры \t{Triangle}, оно будет автоматически браться из заголовочного файла.}

Все параметры (индексы свечек в запросах, а также в возвращаемом вами результате) задаются в \textbf{0-индексации}.

Ваша функция \texttt{solve} с помощью вызовов функции \texttt{compare} должна найти любое разбиение торта на выпуклые кусочки, в котором любые два кусочка не пересекаются по внутренним точкам, суммарная площадь кусочков максимальна, и, возможно, количество кусочков максимально. 

Функция \t{solve} должна вернуть список кусочков, на которые разбивается торт. Каждый кусочек описывается структурой \t{std::vector<int>}, состоящей из свечек, образующих выпуклый многоугольник. Свечки должны быть перечислены \textbf{в порядке следования по границе многоугольника} (по часовой стрелке или против часовой стрелки). Любые два кусочка не должны пересекаться по внутренним точкам. Вы должны вернуть список кусочков, суммарная площадь которых максимально возможная, а в некоторых группах дополнительно требуется максимизировать количество кусочков, при этом сохраняя условие на максимальную возможную суммарную площадь.

За один запуск грейдера \textbf{жюри сделает ровно один вызов функции} \texttt{solve}. \textbf{Грейдер не является адаптивным}, то есть положения свечек фиксируются заранее и не зависят от реализации функции \texttt{solve}.

\Testing

Вам предоставлен шаблон решения \texttt{triangles.cpp}, а так же заголовочный файл \texttt{triangles.h}, содержащий определение функций \texttt{solve} и \texttt{compare}. Для удобства тестирования вам предоставлен грейдер --- файл \texttt{grader.cpp}. В этом файле реализован ввод входных данных со стандартного потока ввода, запуск функции \texttt{solve} и вывод на стандартный поток вывода возвращаемого значения функции \texttt{solve}. В тестирующей системе грейдер может отличаться.

Чтобы скомпилировать ваш код \texttt{triangles.cpp} на языке C++, используйте команду

\begin{verbatim}
g++ -std=c++20 grader.cpp triangles.cpp -o grader
\end{verbatim}

После выполнения данной команды будет создан исполняемый файл грейдера \texttt{grader} или \texttt{grader.exe}, в зависимости от вашей операционной системы, запустив который можно ввести тест в формате, указанном далее.

Если компиляция через команды вызывает у вас трудности, для локального тестирования вы можете скопировать реализацию функции \texttt{solve} в файл \texttt{grader.cpp} (ее необходимо вставить перед функцией \t{main}) и запустить файл \texttt{grader.cpp}. При этом перед отправкой решения в тестирующую систему вам нужно будет оставить только реализацию функции \texttt{solve}, \textbf{не забыв подключить заголовочный файл в начале кода} (это делается с помощью добавления строки \t{\#include "triangles.h"} в начало сдаваемого вами кода). Если вы используете какие либо библиотеки языка C++, их подключение также необходимо добавить в начало отправляемого кода.

\newpage

В случае получения вердикта ошибка компиляции, убедитесь, что \textbf{в отправляемом вами коде не содержится функции \t{main}, а также не содержатся определения функции \t{compare} и структуры \t{Triangle}}. Функцию \t{compare} и структуру \t{Triangle} вы можете только использовать в отправляемом вами коде.
 
\InputFile
Грейдер читает тест в следующем формате:

В первой строке находятся целое число $n$ ($4 \leq n \leq 10\,000$)~--- количество свечек.

В следующих $n$ строках находится по два целых числа $x_i$, $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$) --- координаты $i$-й свечки.
 
\OutputFile
Грейдер выводит результаты функции \texttt{solve} --- список найденных кусочков.

В первой строке выводится число найденных многоугольников (размер вектора, возвращаемого функцией \t{solve}).

В следующих строках для каждого многоугольника (элемента вектора векторов, возвращаемого функцией \t{solve}) в начале выводится размер многоугольника, а в следующей строке номера свечек, являющихся вершинами многоугольника (элементы каждого из \t{std::vector<int>}, входящих в возвращаемое функцией \t{solve} значение). Каждый многоугольник должен быть выпуклым, его вершины должны быть перечислены в порядке следования (по часовой стрелке или против часовой стрелки). Никакие два многоугольника не должны пересекаться во внутренних точках.

В файле \texttt{grader.cpp} есть переменная \texttt{verbose}, которая исходно равна $0$. При увеличении ее значения грейдер будет более подробно писать информацию о вашем решении и его запросах.
 
\Examples
 
\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\end{example}
 
\Note
В первом примере возможная последовательность вызовов функций могла выглядеть так:

\newpage

В начале вызывается функция \t{solve(4)}.

Из функции \t{solve} вызывается функция 

\begin{verbatim}
compare({Triangle(0, 1, 2)}, {Triangle(1, 2, 3)})} 
\end{verbatim}

Во время выполнения функции происходит сравнения размеров треугольных кусочков, образованных треугольником с вершинами в свечках с номерами $0$, $1$ и $2$ и треугольником с вершинами в свечках $1$, $2$, $3$.

Так как первый треугольник меньше второго, то функция возвращает $-1$.

Далее из функции \t{solve} вызывается функция

\begin{verbatim}
compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(0, 1, 3)})}
\end{verbatim}

В ответ будет возвращено $1$, так как площадь треугольника с вершинами в свечках $1$, $2$ и $3$ больше суммарной площади треугольника с вершинами в свечках $0$, $1$ и $2$ и треугольника с вершинами в свечках $0$, $1$ и $3$.

Далее из функции \t{solve} вызывается функция 

\begin{verbatim}
compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(2, 3, 0), Triangle(0, 1, 3)})}
\end{verbatim}

В ответ будет возвращен $0$.

В конце функция \t{solve} возвращает \t{\{\{0, 1, 2\}, \{0, 2, 3\}, \{0, 1, 3\}\}}~--- описание разделения торта на выпуклые кусочки, имеющие максимальную возможную суммарную площадь и не пересекающихся во внутренних точках.

В первом и третьем примере, в найденном способе разрезать торт количество кусочков максимально возможное, поэтому такие ответы считались бы корректными в группах с максимизацией. Во втором тесте количество кусочков не максимально возможное, поэтому такой ответ считался бы корректным в группах без максимизации, но получил бы $0$ баллов в группах с максимизацией.

Обратите внимание, что первый тест подходит под дополнительные ограничения групп $1$ и $2$, а третий тест подходит под дополнительные ограничения группы $5$.
 
 
\Scoring
Тесты к этой задаче состоят из 11 групп. Правила, по которым выставляются баллы за группы описаны ниже. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.

Балл решения за группу тестов равен минимальному баллу, полученному по всем тестам группы.

\begin{itemize}
\item Если ваше решение сделает некорректный вызов \texttt{compare} или вернет ответ, не удовлетворяющий обязательным условиям, оно получит $0$ баллов за тест.
\item В каждом тесте вашему решению разрешается выполнить не более $2 \cdot 10^6$ вызовов функции \texttt{compare}. В случае превышения лимита ваше решение получит $0$ баллов за тест.
\item В части групп требуется максимизировать число кусочков в ответе. В таких группах, если число кусочков будет не максимально возможным, ваше решение получит $0$ баллов за тест.
\end{itemize}

Если ни одно из описанных условий для теста не нарушено, то ответ за тест считается корректным. Пусть полный балл за группу тестов равен $p$. Часть групп оценивается с использованием формулы, часть оценивается без использования формулы:

\begin{itemize}
\item Если группа оценивается без использования формулы, балл за тест равен $p$.
\item Иначе, если группа оценивается с использованием формулы, пусть $q$ это количество вызовов \texttt{compare}, которое сделало ваше решение. Тогда балл за тест равен
$\left\lfloor p \cdot \frac{20n}{\max{(q, 20n)}} \right\rfloor$.
\end{itemize}

\begin{center}
\begingroup
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|c|c|c|c|p{5cm}|}
\hline
\multirow{2}{*}[-0.9ex]{\parbox{1.2cm}{\centering Группа}}
& \multirow{2}{*}[-0.9ex]{\parbox{1.4cm}{\centering Полный\\балл}}
& \multicolumn{2}{c|}{Оценка}
& \parbox{2.2cm}{\centering \vspace{2mm}Доп.\\ограничения\vspace{2mm}}
& \multirow{2}{*}[-0.9ex]{\parbox{1.3cm}{\centering Необх.\\группы}}
& \multirow{2}{*}[-0.9ex]{\parbox{5cm}{\centering Комментарий}}
\\
\cline{3-5}
& & Макс. & Формула & $n$ & & \\
\hline
\hline
0 & 0 & нет & нет & -- & -- & \parbox{5cm}{\centering Тесты из условия.} \\
\hline
\hline
1 & 13 & нет & нет & $n = 4$ & -- & \\
\hline
2 & 4 & да & нет & $n = 4$ & 1 & \\
\hline
\hline
3 & 13 & нет & нет & -- & -- & \parbox{5cm}{\centering \vspace{2mm}$(10^9, -10^9)$, $(-10^9, 10^9)$, $(10^9, 10^9)$ есть в множестве, остальные точки случайные внутри этого треугольника}\vspace{2mm} \\
\hline
4 & 8 & да & нет & -- & 3 & \parbox{5cm}{\centering \vspace{2mm}$(10^9, -10^9)$, $(-10^9, 10^9)$, $(10^9, 10^9)$ есть в множестве, остальные точки случайные внутри этого треугольника}\vspace{2mm} \\
\hline
\hline
5 & 11 & да & да & -- & -- & \parbox{5cm}{\centering \vspace{2mm} точки являются вершинами выпуклого многоугольника \vspace{2mm}} \\
\hline
\hline
6 & 9 & нет & нет & $n \leq 100$ & -- & \parbox{5cm}{\centering точки случайные} \\
\hline
7 & 8 & да & нет & $n \leq 100$ & 6 & \parbox{5cm}{\centering точки случайные} \\
\hline
\hline
8 & 9 & нет & да & -- & -- & \parbox{5cm}{\centering точки случайные} \\
\hline
9 & 8 & да & да & -- & -- & \parbox{5cm}{\centering точки случайные} \\
\hline
\hline
10 & 9 & нет & да & -- & -- & \\
\hline
11 & 8 & да & да & -- & -- & \\
\hline
\end{tabular}
\endgroup
\end{center}

В группах 6 -- 9 все точки были выбраны случайно и независимо из квадрата $[-10^9, 10^9] \times [-10^9, 10^9]$. 

В группах 3 -- 4 точки, кроме $(10^9, -10^9)$, $(-10^9, 10^9)$, $(10^9, 10^9)$, были выбраны случайно и независимо из треугольника с вершинами $(10^9, -10^9)$, $(-10^9, 10^9)$, $(10^9, 10^9)$.

В этих группах среди таких случайных тестов оставлены только те, в которых все точки различные, никакие три не лежат на одной прямой, никакие четыре не образуют трапецию.
 
\end{problem}
