Problem1038--割耳法

1038: 割耳法

[Creator : ]
Time Limit : 3.000 sec  Memory Limit : 128 MB

Submit

Description

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


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


Input

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

Output

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

Sample Input Copy

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

Sample Output Copy

Case 1: 1.4142
Case 2: 10.0499