题目限制

1000 ms 256 M

题目描述

你正在一个城市里旅游，这个城市里有$n$个景点，你需要从$1$号点出发，按顺序访问$2$号点、$3$号点...$n-1$号点、$n$号点并结束冒险，本来是这样的。

但是你感觉有些累，希望跳过其中的若干个点。设你跳过了$k$个点，则你跳过点的花费为：

若$k=0$，则花费为$0$。

若$k>0$，则花费为$2^{k-1}$。

而你路上总花费为：对于未跳过的剩余点，相邻点的距离之和。

需要注意的是，你必须$1$号点出发，$n$号点结束，故$1$号点和$n$号点不允许跳过。

对于平面上两点ab，ab的距离是线段ab的距离，可以使用$sqrt$函数计算：$sqrt((x_a-x_b) * (x_a-x_b)+(y_a-y_b) * (y_a-y_b))$。

现在你希望跳过$0$个或者若干个点，使得自己的跳过景点的花费+路上总花费最小。请你输出一个三位小数表示你的答案。

输入格式

第一行一个正整数$n$表示景点数量。

接下来$n$行，每行两个整数。第$i+1$行表示第$i$个景点的横纵坐标。

输出格式

输出一个三位小数表示最小的跳过景点的花费+路上花费。

数据范围

对于20%的数据，保证$x_i$为0，$y_i$为0或1。

对于40%的数据，保证$n\leq 20$。

对于60%的数据，保证$n\leq 100$。

对于100%的数据，保证$2\leq n \leq 10^5,0\leq x_i,y_i \leq 10000$，不保证每个景点的坐标不同。

输入样例 1

2
0 0
10000 10000

输出样例 1

14142.136

输入样例 2

6
0 0
1 1
2 0
0 1
1 0
2 1

输出样例 2

5.828

样例解释

样例解释1

尽管$1$号点到$2$号点距离很大，但不允许跳过$1$和$n$号点，所以不得不走完全程，距离为$10000 * \sqrt{10000}\approx{14142.136}$。

样例解释2

你可以跳过$3$、$4$号点，经过$1$、$2$、$5$、$6$号点。所需花费如下：

$1$号点至$2$号点花费为$\sqrt{2}$

$2$号点至$5$号点花费为$1$

$5$号点至$6$号点花费为$\sqrt{2}$

跳两个点，花费为$2^1=2$。

总花费为$3+2 * \sqrt{2}$。