这道题的实质是求一种划分方案，即用 ( N - 3 ) 条连接给定的凸 N 边形的顶点的线段将凸多边形划分为 ( N - 2 ) 个互不重叠的三角形，使得这些三角形面积的方差最小。

　　我们不难发现，这道题是具有最优子结构性质的。由于这些三角形的面积总和就是给定的凸多边形的面积，所以用凸多边形的面积除去 ( N - 2 ) 就得到三角形面积的平均值，这是一个定值。因此，我们的目标就转化为求出一种划分方案，使得各个三角形面积与该定值的差的平方的总和最小。对于当前的凸多边形，按连续三个顶点划分出一个三角形之后，大问题就转化成求剩下的凸多边形最优划分方案的子问题。由此看来，该题的最优子结构性质是成立的。

　　那么，我们该如何来实现呢？我们很容易想出这样一种实现方法：我们用 F ( a1, a2, a3 ) 表示以 编号为 A1，A2，A3 的顶点组成的三角形面积与平均值的差的平方。C ( S ) ，S={A1，A2，~ An }表示凸多边形A1，A2，~An的最优划分方案值。于是我们得到动态规划方程：C ( S ) = min {C ( Si ) + F ( ai-1,ai,ai+1),其中 S- Si= {ai} } 。如果我们这样做，就有必要开一个数组来存储每一个凸多边形的最优值，该数组的大小= ，当 N 较大时，所需空间指数级增长；并且对于一个N 边形，我们要通过比较 N 种情况，才能得到其最优值，而每次按连续三个顶点划分出

一个三角形之后，得到的是一个N-1边形，又要通过 N-1次比较求出它的最优值。由此从所需空间和时间的角度来看，这种做法很不理想，虽然比搜索好得多，但仍然不能有效地解决问题。

　　我们能否利用该题的最优子结构性质列出一个新的动态规划方程呢？我们不妨用C ( m , i ) 表示以顶点 i 开始逆时针形成的M边形的最优值。如图一中，C ( 4，2 ) 表示四边形A2，A3，A4，A5 的最优值；C ( 5，4 ) 就表示五边形A4，A5，A6，A1，A2 的最优值。新的动态规划方程是：C ( m , i ) = min{C ( k+1, i)+C ( M-K， I+K ) +F ( I，I+K，M+I-1)} ，其中 1<=K<=M-2}。同时我们规定，当M<3 时，C( M，I ) =0；当M=3 时，C ( M，I )=F ( I+1，I ，I-1) 。例如图2 中 ，ABCD四图分别是当K=1，2，3，4 时 C ( 6，1 ) 的分割情况。

　　这样，程序实现所需空间只要N^2，而时间复杂度也只有O ( N^3 )。

　　这道题还考察了一些几何知识 ，因此 ，我们要熟悉一些几何算法，才能完整地解决这道题。 以下是大致的实现过程：

　　1、读入各点坐标。由于数据给出的坐标是无序的，我们要对其进行顺时针或逆时针排序。
　　2、将凸多边形任意划分为 ( N-2 ) 个互不重叠的三角形，利用海伦公式逐个求出面积，再算出面积平均值。
　　3、初始化数组C，当M<3 时，C ( M ，I ) =0；当 M=3 时， C ( M，I )=F ( I-1，I，I+1)；当M=4 时， C ( M，I ) = MIN { F ( I，I+1，I+2 )+F ( I，I+2，I+3 )，F ( I，I+3，I+2 ) +F ( I+2，I+3，I+1 ) }。
　　4、计算出从各个顶点开始的M边形的最优值，M=5,6 ~ N。
　　5、比较 C ( N，I )，I=1,2,~N，取最小者，输出。