\textbf{Тази задача може да се реши само на език за програмиране C++.}

Организаторите на Закретата ученическа олимпиада по програмиране решили да поръчат огромна торта за тържествената вечеря. За целта, те поръчали торта с $n$ свещички, номерирани от $0$ до $n-1$. Известно е, че свещичките се намират в различни точки от равнината, никои тре свещички не лежат на една права, Никои четири свещички не образуват трапец(четириъгълник с две успоредни страни).

За да има парче торта за всеки, организаторите искат предварително да опишат начин за разрязване на тортата на максимален брой парчета. За съжаление, вие не знаете разположението на свещичките върху тортата, а единствения достъпен начин да се разбере, как изглежда тортата е кореспонденция със сладкърницата по електронната поща.

В едно съобщение можете да поискате да се претеглят не повече от четири триъгълни парчета, с върхове в свещички:

\begin{itemize}
\item Предоставяте два списъка с триъгълници \texttt{left} и \texttt{right}, общо съдържащи не повече от четири триъгълника. Триъгълниците може да се пресичат, да имат общи свещи и даже да съвпадат.
\item В сладкарницата ще изрежаттриъгълни парчета, съответстващи на изпратения списък от няколко копия на тортата и ще сложат парченцата от \texttt{left} на лявата чаша на везната, а парченцата от \texttt{right} на дясната чаша на везната.
\item След това ви изпращат резултата от претеглянето. Приема се, че теглото на парчето е равно на неговата площ. В резултат на това вие ще разберете, в кой от двата списъка от триъгълници общата площ е по-голяма, или че площите съвпадат.
\end{itemize}

След няколко претегляния, вие трябва да можете да намерите начин за разрязване на тортата. Всяко парче трябва да бъде изпъкнал многоъгълник с върхове в свещички. Върховете на дадено парче трябва да бъдат изброени по посока на часовниковата стрелка или обратно на часовниковата стрелка. Никои две парчета не трябва да се пресичат във вътрешна точка. Трябва да върнете списък с парчета, чиято обща площ е възможно най-голяма. В някои групи може също да искате да увеличите максимално броя на парчетата.

\SolutionFormat

Това е нестандартна задача. Формата на тестването и е с грейдър и затова вие трябва да реализирате само функция \t{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++, тяхното включване също трябва да бъде добавено в началото на изпращания код.


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