어느 맑은 밤, 천문학자 하린이는 망원경으로 관측한 별 \(N\) 개의 위치를 평면 좌표 \((x, y)\) 로 기록했다. 하린이는 이 별들을 모두 감싸는 가장 작은 볼록한 울타리를 치고 싶다.

여기서 '가장 작은 볼록한 울타리'란, 모든 별을 내부 또는 경계에 포함하는 볼록 다각형 중에서 둘레가 가장 짧은 것을 말한다. 이는 곧 별들의 볼록 껍질(convex hull) 이며, 울타리의 둘레는 그 껍질을 이루는 변들의 길이의 합과 같다.

별들의 좌표가 주어질 때, 모든 별을 감싸는 가장 작은 볼록 울타리의 둘레 길이를 구하는 프로그램을 작성하라.

(주의: 모든 별이 한 직선 위에 놓여 있는 경우, 울타리는 그 선분을 양쪽에서 감싸는 형태가 되어 둘레는 선분 길이의 \(2\) 배가 된다.)

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

\(-1{,}000{,}000 \le x, y \le 1{,}000{,}000\)

별이 하나뿐이거나 모든 별이 한 점에 모여 있으면 둘레는 \(0\) 이다.

첫째 줄에 별의 개수 \(N\) (\(1 \le N \le 100{,}000\)) 이 주어진다.

다음 \(N\) 개의 줄에는 각 별의 좌표를 나타내는 두 정수 \(x\), \(y\) (\(-1{,}000{,}000 \le x, y \le 1{,}000{,}000\)) 가 주어진다. 같은 좌표에 두 개 이상의 별이 있을 수도 있다.

모든 별을 감싸는 가장 작은 볼록 울타리의 둘레 길이를 출력한다. 정답과의 절대 또는 상대 오차가 \(10^{-6}\) 이하이면 정답으로 인정한다.

riseoj 작성

출처 Original