Problem #188 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

在欧几里得旅行商问题中，给定平面上 $n$ 个点作为输入，希望求出连接所有 $n$ 个点的最短巡游路线。图 (a) 给出了一个 7 点问题的解。此问题是 NP 难问题，因此大家相信它并不存在多项式时间内的求解算法。

J.L.Bentley 建议将问题简化，限制巡游路线为双调巡游 (bitonic tours)，即从最左边的点开始，严格向右前进，直至最右边的点，然后调头严格向左前进，直至回到起始点。图 (b) 给出了相同 7 个点的最短双调巡游路线。问题简化之后，存在一个多项式时间的算法。

第一行一个数 $n$ ，表示共有 $n$ 个点 $(2 ⩽ n ⩽ 10^{4})$ 。
接下来 $n$ 行，每行两个整数 $x_{i}, y_{i} (| x_{i} |, | y_{i} | ⩽ 10^{5})$ 表示第 $i$ 个点的坐标（保证 $x_{i}$ 互不相同）。

输出一个浮点数，表示双调巡游距离的最小值。(要求误差不超过 $10^{- 3}$ )

Input

Output

6.47214

Input

Output

788.635e-02

10 人解决，30 人已尝试。

11 份提交通过，共有 359 份提交。

7.8 EMB 奖励。

创建: 6 年，12 月前.

修改: 6 年，8 月前.

最后提交: 2 周，3 天前.

来源: N/A

DP

188. 双调巡游