程序设计能力实训

1186. 双调巡游

单点时限: 2.0 sec

内存限制: 256 MB

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

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

输入格式

第一行一个数 ,表示共有 个点
接下来 行,每行两个整数 表示第 个点的坐标(保证 互不相同)。

输出格式

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

样例

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
不限期开放

题目列表