R00258
천문대 관측 영역
골드 I레이팅
의견: 0
설명
한 천문대가 평면 위에 \(N\)개의 관측 지점을 설치했다. 모든 좌표는 정수이다. 이 지점들을 모두 포함하는 가장 작은 볼록 다각형(볼록 껍질)의 넓이를 구하려고 한다.
넓이가 분수가 되는 것을 피하기 위해, 넓이의 두 배를 정수로 출력한다. (볼록 껍질의 넓이는 항상 \(\frac{1}{2}\)의 정수배이므로, 넓이의 두 배는 언제나 정수이다.)
모든 점이 한 직선 위에 있거나 서로 다른 점이 둘 이하여서 다각형을 이룰 수 없으면 넓이는 \(0\)이며, \(0\)을 출력한다.
제약
\(1 \le N \le 100\,000\)
\(-10^9 \le x, y \le 10^9\)
입력 형식
첫째 줄에 관측 지점의 개수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 지점의 좌표 \(x\), \(y\)가 주어진다. 같은 좌표가 중복되어 주어질 수 있다.
출력 형식
볼록 껍질 넓이의 두 배를 정수로 한 줄에 출력한다.
예제 1
입력
4
0 0
4 0
4 3
0 3출력
24설명
\(4 \times 3\) 직사각형의 넓이는 \(12\)이고, 그 두 배인 \(24\)를 출력한다.
예제 2
입력
3
0 0
2 0
4 0출력
0설명
세 점이 한 직선 위에 있어 넓이가 \(0\)이므로 \(0\)을 출력한다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
천문대 관측 영역
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
천문대 관측 영역
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기