볼록 껍질 넓이

문제

2차원 평면 위에 $N$개의 점이 주어진다. 이 점들 중 볼록 껍질(convex hull)을 구성하는 점들을 찾고, 그 볼록 껍질이 감싸는 영역의 넓이의 2배를 정수로 구하라.

볼록 껍질이란 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형을 뜻한다.

입력

첫째 줄에 점의 개수 $N$이 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 $x, y$ 좌표가 공백으로 구분되어 주어진다.

제한

• $3 \le N \le 100,000$
• $-10^9 \le x, y \le 10^9$
• 모든 좌표는 정수다.
• 모든 점이 한 직선 위에만 있는 경우는 주어지지 않는다.

출력

볼록 껍질의 넓이에 2를 곱한 값을 정수로 출력하라. 넓이의 2배는 항상 정수임이 보장된다.

예제 입력 1

4
0 0
4 0
4 4
0 4

예제 출력 1

32

예제 입력 2

3
0 0
3 0
0 4

예제 출력 2

12