해자 만들기

농부 존은 목마른 땅돼지 떼의 침입으로부터 농장을 지키기 위해 농장 둘레에 해자(moat)를 파려고 한다. 농장에는 서로 다른 정수 좌표에 놓인 물웅덩이가 $N$개 있으며, 해자는 물웅덩이 사이를 잇는 직선 구간들로 판다.

해자는 모든 물웅덩이를 감싸야 한다. 즉, 각 물웅덩이는 해자 선 위에 있거나 그 안쪽에 있어야 하고, 해자는 하나의 닫힌 고리를 이루어야 한다. 땅을 파는 일은 비용이 크기 때문에 존은 해자의 길이를 최소로 하고 싶다. 만들 수 있는 가장 짧은 해자의 길이를 구하라.

(이 길이는 물웅덩이들의 볼록 껍질(convex hull)의 둘레와 같다.)

제약 조건

• $8 \le N \le 5000$
• 모든 좌표는 $1 \le x, y \le 45000$인 정수이다.
• 모든 물웅덩이의 위치는 서로 다르며, 어떤 세 물웅덩이도 한 직선 위에 있지 않다.

아래 격자에서 20개의 *는 물웅덩이이고, 이를 둘러싼 선은 이들을 감싸는 가장 짧은 고리를 나타낸다:

...*-----------------*......
../..........*........\.....
./.....................\....
*......................*\...
|..........*........*....\..
|*........................\.
|..........................*
*..........................|
.\*........................|
..\.....................*..|
...\........*............*.|
....\..................*...*
.....\..*..........*....../.
......\................../..
.......*----------------*...

맨 위 변에서 시작하여 각 구간의 변위는 $(18,0)$, $(6,-6)$, $(0,-5)$, $(-3,-3)$, $(-17,0)$, $(-7,7)$, $(0,4)$, $(3,3)$이며, 전체 길이는 $70.8700576850888\ldots$이다. 소수점 아래 두 자리까지 출력하면 답은 $70.87$이다.

• 첫째 줄: 정수 $N$ 하나.
• 둘째 줄부터 $N+1$번째 줄까지: 공백으로 구분된 두 정수 $X_i$와 $Y_i$. 물웅덩이 하나의 좌표이다.

• 가장 짧은 해자의 길이 $D$를 소수점 아래 정확히 두 자리까지 한 줄에 출력한다.