Building the Moat To repel the invading thirsty aardvarks, Farmer Ran wants to build a moat around his farm. He owns N (3 <= N <= 50,000) watering holes, and will be digging the moat in a straight line between pairs of them. His moat should protect (i.e., surround) all his watering holes; every watering hole must be on or inside the moat, and the moat must form a closed loop. Digging a moat is expensive work, and FR wants his moat to have the minimum length possible. Find the length of the shortest moat he can construct. The unique holes are each located at integer coordinates in the range -20,000..20,000. Consider this grid where the 20 '*'s represent watering holes: ...*-----------------*...... ../..........*........\..... ./.....................\.... *......................*\... |..........*........*....\.. |*........................\. |..........................* *..........................| .\*........................| ..\.....................*..| ...\........*............*.| ....\..................*...* .....\..*..........*....../. ......\................../.. .......*----------------*... The enclosing lines are the shortest possible path that can enclose this set of watering holes. The line displacements, starting with the top line are: (18,0), (6,-6), (0,-5), (-3,-3), (-17,0), (-7,7), (0,4), and (3,3). This yields a distance of 70.8700576850888(...). PROBLEM NAME: moat.X INPUT FORMAT: * Line 1: A single integer, N. * Lines 2..N+1: Two space-separated integers, X_i and Y_i that specify the location of a watering hole. SAMPLE INPUT: 20 2 10 3 7 22 15 12 11 20 3 28 9 1 12 9 3 14 14 25 6 8 1 25 1 28 4 24 12 4 15 13 5 26 5 21 11 24 4 1 8 OUTPUT FORMAT: * Line 1: A single number D, the shortest possible length of moat. accurate to the hundredths place. SAMPLE OUTPUT: 70.87