Тесты к этой задаче состоят из 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)$.

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