한 천문대가 평면 위에 \(N\)개의 관측 지점을 설치했다. 모든 좌표는 정수이다. 이 지점들을 모두 포함하는 가장 작은 볼록 다각형(볼록 껍질)의 넓이를 구하려고 한다.

넓이가 분수가 되는 것을 피하기 위해, 넓이의 두 배를 정수로 출력한다. (볼록 껍질의 넓이는 항상 \(\frac{1}{2}\)의 정수배이므로, 넓이의 두 배는 언제나 정수이다.)

모든 점이 한 직선 위에 있거나 서로 다른 점이 둘 이하여서 다각형을 이룰 수 없으면 넓이는 \(0\)이며, \(0\)을 출력한다.

\(1 \le N \le 100\,000\)

\(-10^9 \le x, y \le 10^9\)

첫째 줄에 관측 지점의 개수 \(N\)이 주어진다.

다음 \(N\)개의 줄에 각각 지점의 좌표 \(x\), \(y\)가 주어진다. 같은 좌표가 중복되어 주어질 수 있다.

볼록 껍질 넓이의 두 배를 정수로 한 줄에 출력한다.

riseoj 작성

출처 Original