单点时限: 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}$)
3 1 1 2 3 3 1
6.47214
4 3 1 4 2 1 1 2 3
788.635e-02