Dune Dash

문제

You signed up for the Dune Dash, a running race across the desert. Everything went well — except that in the excitement, you forgot to start StrideTrack, the app that records how far you’ve run. All you have now are the official checkpoint locations, but not the order in which you passed through them.

Formally, the race consisted of $NN$ checkpoints, each given by its coordinates in the Euclidean plane. The sequence in which they were visited is unknown to you, but the organizers designed the course to prevent anyone from straying off route. In particular, if $q_1,q_2,\dots ,q_{N}q\_1,\; q\_2,\; \backslash dots,\; q\_N$ is the correctly ordered list of the checkpoints along the race, then for every triple it holds that

$$\text{dist}(q_i,q_k)>\max (\text{dist}(q_i,q_j),\text{dist}(q_j,q_k))\backslash text\{dist\}(q\_i,\; q\_k)\; >\; \backslash max(\backslash text\{dist\}(q\_i,\; q\_j),\; \backslash text\{dist\}(q\_j,\; q\_k)\; )$$

where $\text{dist}(p,q)\backslash text\{dist\}(p,q)$ denotes the Euclidean distance between points $pp$ and $qq$. Your task is to determine the total length of the race.

Figure D.1: Illustration of sample 2. The dashed line shows where the race went.

입력

The first line consists of the integer $NN$ ($2\le N\le 2\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\; \backslash cdot\; 10^5$). The following $NN$ lines each contain two integers $x_{i}x\_i$ and $y_{i}y\_i$ ($-{10}^9\le x_i,y_i\le {10}^9-10^9\; \backslash leq\; x\_i,\; y\_i\; \backslash leq\; 10^9$). These are the coordinates of each checkpoint.

The checkpoints are not necessarily in the order in which they were visited during the race. It is guaranteed that there is some ordering of the checkpoints such that they satisfy the distance requirements above.

The $NN$ points given in the input are all distinct.

출력

Print one floating point number, the length of the race. Your answer will be correct if it has an absolute or relative error of at most ${10}^{-6}10^\{-6\}$.

3
1 0
0 0
1 1

2.0

10
-1 -7
-1 -11
0 -9
2 2
1 -2
2 -1
3 1
-1 -5
0 -3
-3 -11

17.186912597118443