| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 3 | 1 | 1 | 33.333% |
Том расставил по дому несколько мышеловок. Дом может быть представлен как бесконечная двумерная плоскость. Мышеловка номер $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$). Гарантируется, что никакие две мышеловки не находятся в одной точке.
Выведите одно целое число --- удвоенную площадь минимальной по площади защищенной области, которую Джерри может получить. Можно доказать, что удвоенная площадь защищенной области всегда будет целым числом.
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