#hah952. 哈密顿路径（splitham）

时间限制：5 s       空间限制：512 MiB       标签： 动态规划 

算法难度等级：0       思维难度等级：0       实现难度等级：0

哈密顿路径问题是指：找一条经过全部 $n$ 个点恰好一次的路径。

为了解决平面直角坐标系上的哈密顿路径问题，dottle 设计了这样一个算法：

设当前有 $n$ 个点，他们的横坐标互不相同，纵坐标也互不相同。

现在给出解决点集 $S$ 的算法：

• 将 $S$ 分成左右两部分，从左右两个集合中选一个，先走完这个集合的点，再走另一个集合的点；
• 在走左边或者右边的集合的时候，将该集合分成上下两部分。从上下两个集合中选一个，先走完这个集合的点，再走另一个集合的点；
• 在走上面或者下面的集合的时候，将该集合分成左右两部分。从左右两个集合中选一个，先走完这个集合的点，再走另一个集合的点；
• 以此类推，直到点集内只有一个点时停止分割。

把点集 $X$ 分成左右两部分指将 $X$ 内的点根据横坐标排序，横坐标较小的 $\lfloor |X|/2\rfloor $ 个点被分在左边的集合，其余的点被分在右边的集合。

把点集 $X$ 分成上下两部分指将 $X$ 内的点根据纵坐标排序，纵坐标较小的 $\lfloor |X|/2\rfloor $ 个点被分在上面的集合，其余的点被分在下面的集合。

如果你找出的路径分别是 $p_{1\sim n}$，那么它的总长度为 \sum_{i=1}^{n-1}{\rm dis}(p_i,p_{i+1})。其中 {\rm dis}(a,b) 指编号为 $a$ 与 $b$ 的点的欧几里得距离，即 $\sqrt{(x_a-x_b)^2+(y_a-y_b)^2}$。

请你求出，在满足算法要求的前提下，你找出的路径的最小总长度是多少。输出它作为答案，四舍五入到两位小数。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行每行两个正整数 $x,y$，描述了一个点的坐标。

输出格式

一行一个两位小数作为答案。

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

18.20

样例 2

见选手目录下的 splitham/splitham2.in 和 splitham/splitham2.ans。

样例 3

见选手目录下的 splitham/splitham3.in 和 splitham/splitham3.ans。

样例解释

最优的路径是：$4~7~2~6~1~5~3~8$。

过程如下：

1. 我们把点集分为左右两部分，$1,3,5,8$ 被分到左边，$2,4,6,7$ 被分到右边；我们决定先走右边。
2. $2,4,6,7$ 被分成了上下两部分，$2,6$ 被分到上面，$4,7$ 被分到下面；我们决定先走下面；
3. $4,7$ 被分成了左右两部分 $7$ 和 $4$，我们决定先走 $4$ 再走 $7$；
4. $2,6$ 被分成了左右两部分 $2$ 和 $6$，我们决定先走 $2$ 再走 $6$；
5. $1,3,5,8$ 被分成了上下两部分，$1,5$ 被分到上面，$3,8$ 被分到下面；我们决定先走 $1,5$。
6. 后略。

数据范围

保证 $1\le n\le 500$，$1\le x,y\le 2000$。

对于测试点 $1\sim 3$，保证 $n\le 6$；

对于测试点 $4\sim 7$，保证 $n\le 50$；

对于测试点 $3\sim 4$，保证每个点横纵坐标都相等。