Description

你报名参加了 Dune Dash（沙丘冲刺），一项横穿沙漠的长跑比赛。一切都很顺利——除了在兴奋之中，你忘记启动 StrideTrack，那款记录你已跑距离的应用程序。现在你仅剩下官方检查点的位置，但却不知道你通过它们的先后顺序。

形式化地说，比赛包含 $N$ 个检查点，每个检查点由其在欧几里得平面上的坐标给出。你经过这些点的顺序未知，但赛事组织者设计赛道时保证选手无法偏离路线。具体而言，如果 $q_1, q_2, \dots, q_N$ 是比赛过程中正确的检查点访问顺序，那么对于所有满足 $i<j<k$ 的三元组，都有：

$$\text{dist}(q_i, q_k) \;>\; \max\bigl(\text{dist}(q_i, q_j),\ \text{dist}(q_j, q_k)\bigr)$$

其中 $\text{dist}(p,q)$ 表示点 $p$ 与点 $q$ 的欧几里得距离。你的任务是确定比赛的总长度。

:::align{center}

样例 2 的示意图。虚线表示实际赛道。 :::

Input Format

第一行包含整数 $N$（$2 \le N \le 2 \cdot 10^5$）。
接下来的 $N$ 行中，每行包含两个整数 $x_i$ 与 $y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示检查点的坐标。

检查点的输入顺序不一定为实际经过顺序。

保证存在某种排列方式使得检查点满足上述距离条件。

输入中的 $N$ 个点均两两不同。

Output Format

输出一个浮点数，即比赛总长度。

当你的答案的绝对误差或相对误差不超过 $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

Hint

翻译由 ChatGPT-5 完成