Building the Moat

Farmer John wants to protect his farm from invading, thirsty aardvarks by digging a moat around it. He has $N$ watering holes, each at a distinct integer coordinate, and he will dig the moat as straight segments that run between pairs of holes.

The moat must enclose every watering hole: each hole must lie on or inside the moat, and the moat must form a single closed loop. Digging is expensive, so Farmer John wants the moat to be as short as possible. Find the length of the shortest moat he can build.

(Equivalently, this length is the perimeter of the convex hull of the watering holes.)

Constraints

• $8 \le N \le 5000$
• Every coordinate is an integer with $1 \le x, y \le 45000$.
• All holes lie at distinct positions, and no three holes are collinear.

In the grid below, the 20 * marks are watering holes and the surrounding lines show the shortest loop that encloses them:

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

Starting from the top edge, the segment displacements are $(18,0)$, $(6,-6)$, $(0,-5)$, $(-3,-3)$, $(-17,0)$, $(-7,7)$, $(0,4)$, and $(3,3)$, giving a total length of $70.8700576850888\ldots$. Printed to two decimal places, the answer is $70.87$.

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: two space-separated integers $X_i$ and $Y_i$, the coordinates of one watering hole.

• A single line containing one number $D$, the length of the shortest possible moat, printed to exactly two decimal places.