程序设计能力实训

1186. 双调巡游

单点时限: 2.0 sec

内存限制: 256 MB

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

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

输入格式

第一行一个数 $n$,表示共有 $n$ 个点 $(2\leqslant n \leqslant 10^4)$。
接下来 $n$ 行,每行两个整数 $x_i, y_i(|x_i|,|y_i| \leqslant 10^5)$ 表示第 $i$ 个点的坐标(保证 $x_i$ 互不相同)。

输出格式

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

样例

Input
3
1 1
2 3
3 1
Output
6.47214
Input
4
3 1
4 2
1 1
2 3
Output
788.635e-02
不限期开放

题目列表