Том расставил по дому несколько мышеловок. Дом может быть представлен как бесконечная двумерная плоскость. Мышеловка номер $$$i$$$ находится в точке $$$(x_i, y_i)$$$.
Выпуклой оболочкой множества точек называется минимальный по площади выпуклый многоугольник (возможно, вырожденный), содержащий внутри или на границе все точки из множества.
Том считает защищенной область, соответствующую выпуклой оболочке точек, в которых расположены мышеловки.
Джерри может обезвредить ровно одну мышеловку. В результате, защищенная область уменьшится до выпуклой оболочки оставшихся мышеловок. Помогите Джерри определить, какой минимальной по площади защищенной области он может добиться.
В первой строке дано одно целое число $$$n$$$ — количество мышеловок ($$$2 \le n \le 100\,000$$$).
В следующих $$$n$$$ строках дано по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-й мышеловки ($$$|x_i|, |y_i| \le 10^9$$$). Гарантируется, что никакие две мышеловки не находятся в одной точке.
Выведите одно целое число — удвоенную площадь минимальной по площади защищенной области, которую Джерри может получить. Можно доказать, что удвоенная площадь защищенной области всегда будет целым числом.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 23 | $$$n \le 1\,000$$$ | первая ошибка | |
| 2 | 21 | Точки образуют строго выпуклый невырожденный многоугольник и даны в порядке обхода против часовой стрелки | первая ошибка | |
| 3 | 27 | Количество точек, находящихся строго внутри выпуклой оболочки, не превышает $$$10$$$ | 2 | первая ошибка |
| 4 | 29 | Без дополнительных ограничений | 1–3 | первая ошибка |
2 1 2 3 4
0
4 1 1 0 1 0 0 1 0
1
6 0 0 5 0 5 5 0 5 2 1 2 4
30
