\begin{tutorial}{Играем в го}

\begin{center}
\textit{Автор задачи: Алексей Михненко, разработчик: Игорь Маркелов}
\end{center}

Для начала посмотрим на оптимальный ответ. Очевидно, что площадь ответа будет не меньше, чем площадь выпуклой оболочки исходного множества точек. В случае, если площадь больше, утверждается, что белая точка которую мы подвинули сдвинута относительно нормали к одному из $n \cdot (n - 1) / 2$ отрезков соединяющих исходные точки.

Это наблюдение дает нам возможность написать решение за $O(n^4 \cdot \log(n))$ ~--- переберем направление и точку, сдвинем, пересчитаем оптимальный ответ через площадь выпуклой оболочки полученного множества.

Заметим (разумеется, доказательство этого потрясающего наблюдения остается в качестве интереснейшего упражнения для любознательного читателя), что для каждого ориентированного направления достаточно рассмотреть не более $5$ точек (наиболее удаленных по этому направлению). Таким образом предыдущее решение превращается в $O(n^3 \cdot \log(n))$, если для каждого направления в начале выбирать не более $5$ кандидатов, а затем для каждого из них строить выпуклую оболочку.


Научимся для зафискированного множества из $k$ точек отвечать на запрос <<площадь выпуклой оболочки множества, если добавить в него еще одну точку>> за $O(\log(k))$ с предподсчетом за $O(k \cdot \log(k))$. Построим выпуклую оболочку на $k$ точках, посчитаем префиксные суммы площадей выпуклой оболочки от первой вершины до $i$-й для всех вершин. Для ответа на запрос, в начале стандартным алгоритмом за $O(\log(k))$ проверим, лежит ли точка внутри выпуклой оболочки. В случае, если лежит ~--- ответ равен площади исходной оболочки. В случае, если не лежит ~--- найдем касательные из точки к выпуклой оболочке, площадь ответа будет равна площади треугольника из точек касание и точки для которой мы отвечаем на запрос к которой нужно прибавить площадь исходной выпуклой оболочки без части многоугольника отрезаемой диагональю между точками касания. Поиск касательных можно реализовать за $O(\log(k))$, а необходимые площади вычислить за $O(1)$ воспользовавшись предподсчитанными префиксными суммами.

Применим этот примитив к предыдущему решению, предподсчитаем выпуклые оболочки исходного множества без каждой из белых точек, тогда решение будет работать за $O(n^3)$, так как самая тяжелая часть это рассмотрение $O(n)$ точек-кандидатов для $O(n^2)$ направлений.

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

Оптимизируем эту часть с помощью стандартной техники вращающегося сканлайна по направлениям. Для $O(n^2)$ направлений требуется поддерживать отсортированный вдоль направления список из $O(n)$ точек. Суммарное количество событий будет $O(n^2)$, соответственно теперь решение будет работать за $O(n^2 \cdot \log(n))$.

\end{tutorial}
