24235번 - 유산 스페셜 저지

문제

조상때부터 대대로 물려받던 땅이 있다. 땅이 매우 크기 때문에 $N$개 위치를 좌표평면 위에 점으로 표시를 해놓았다. 땅은 $N$개의 점을 모두 포함하는 가장 작은 볼록다각형이다.

이 땅을 두 명한테 나눠주려고 한다. 나눠주는 땅의 넓이가 같도록 해야 싸움이 일어나지 않을 것이기 때문에 $y$축이랑 평행한 직선 $x = a$를 그어 나눠지는 두 땅의 넓이가 같도록 하려고 한다.

[그림 1]처럼 좌표평면에 9개 점이 존재한다고 가정해보자.

[그림 1] 9개의 점을 좌표평면에 표시

땅을 표시하는 좌표평면 정보에서 땅은 9개의 점을 모두 포함하는 가장 작은 볼록다각형이기 때문에 [그림 2]와 같다.

[그림 2] 좌표평면에 땅에 해당하는 부분 표시

두 명이 이 땅을 넓이가 같도록 나눠야 하기 때문에 [그림 3]처럼 직선을 그어 두 땅의 넓이가 같도록 구분하면 된다.

[그림 3] 두 땅의 넓이가 같도록 $x = a$ 직선으로 구분

땅의 정보가 주어졌을 때 같은 면적의 땅을 나눌 수 있도록 $a$의 값을 찾아주자.

입력

첫째 줄에 깃발의 개수 $N$ (3ドル ≤ N ≤ 500,000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 깃발이 위치한 좌표 $x,ドル $y$ ($-10^{9} ≤ x, y ≤ 10^{9}$)가 공백으로 구분되어 주어진다. 중복된 좌표가 없음과 볼록다각형의 넓이가 항상 0보다 큰 것을 보장한다.

입력으로 주어지는 모든 값은 정수이다.

출력

$a$의 값을 출력한다. 모범 답안과의 절대/상대 오차가 10^-3 이하인 경우 정답으로 인정된다.

제한

힌트