1902_算法设计例题：凸多边形最优三角剖分（DP）

给定凸多边形P各顶点坐标集{v₀，v₁，…，v_n-1}，保证各顶点坐标依逆时针次序给出。定义由多边形的边和弦组成的三角形上的权函数w(v_iv_jv_k) = |v_iv_j| + |v_jv_k| + |v_kv_i|，相应于此权函数的最优三角剖分即为最小弦长三角剖分。

其中|v_iv_j|是点v_i到v_j的欧氏距离。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即该三角剖分中诸三角形上权之和为最小。输出该最小值。

设v_i= (x₁, y₁), v_j = (x₂, y₂)，则v_i和v_j的欧氏距离 = sqrt( (x₁-x₂)*(x₁-x₂) + (y₁-y₂)*(y₁-y₂) );

输入的第一行为一个整数n ( 3 ≤ n ≤ 100 )，表示凸多边形P的顶点数。

接下来有n行，每行由两个整数组成，表示顶点的欧氏坐标x和y。( 0 ≤ x, y ≤ 1000 )，按照顺时针方向输入。

输出只有一个整数，表示凸多边形P的三角剖分中诸三角形上权值和的最小值，结果保留小数点后3位。

4
0 0
0 1
1 1
1 0

1.414

如上图，假设上图为最优解的情况，则输出的最小值为：|v₁v₃|+|v₀v₃|+|v₃v₆|+|v₄v₆|.