1149 : 割耳法

Description

割耳法可以把一个多边形切成三角形：每次沿着某条对角线切下来一个三角形（称为“耳朵”），n-3次就能把一个n边形切成一个三角形。如下图，三角形{2,3,4}被割掉了。

输入一个多边形，怎样做才能让每次切割痕迹的总长度最小？

Input

输入最多包含30组测试数据。每组数据第一行为多边形的顶点数n(4<=n<=100)。以下n行描述多边形的各个顶点，按照逆时针或者顺时针排列。

Output

对于每组数据，输出切割痕迹总长度的最小值，保留4位小数。

Sample

4
0 0
3 0
1 1
0 3
4
0 0
10 0
10 1
0 1

Case 1: 1.4142
Case 2: 10.0499

Hint

Source

Author

SRbGa