Мышеловки

시간 제한2초메모리 제한1024 MB

요약

점이 최대 100,000개 주어질 때, 한 점을 정확히 하나 제거한 나머지 점들의 볼록 껍질 넓이가 최소가 되도록 하고 그 넓이의 두 배를 출력한다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Том расставил по дому несколько мышеловок. Дом может быть представлен как бесконечная двумерная плоскость. Мышеловка номер $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$ ). Гарантируется, что никакие две мышеловки не находятся в одной точке.

출력

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

예제3

예제 1
입력
```
2
1 2
3 4
```
예상 출력
```
0
```
예제 2
입력
```
4
1 1
0 1
0 0
1 0
```
예상 출력
```
1
```
예제 3
입력
```
6
0 0
5 0
5 5
0 5
2 1
2 4
```
예상 출력
```
30
```