1014. 旅行商简化版

时间限制 1000 ms
内存限制 128 MB

题目描述

著名的NPC难题的简化版本

现在笛卡尔平面上有n(n< =1000)个点,每个点的坐标为(x,y)(-2^31< x,y< 2^31,且为整数),任意两点之间相互到达的代价为这两点的欧几里德距离,现要你编程求出最短bitonic tour。

输入数据

第一行一个整数 $n$

接下来 $n$ 行,每行两个整数 $x,y,$ 表示某个点的坐标。

输入中保证没有重复的两点,
保证最西端和最东端都只有一个点。

输出数据

一行,即最短回路的长度,保留 $2$ 位小数。

样例输入

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

样例输出

25.58

题目信息

未提交
未通过无法查看
未通过无法查看