用动态规划解决矩形覆盖问题

Question

··有没有大神会那个矩阵覆盖问题啊？就是在POJ中的~~求解代码
描述
在平面上给出了n个点，现在需要用一些平行于坐标轴的矩形把这些点覆盖住。每个点都需要被覆盖，而且可以被覆盖多次。每个矩形都至少要覆盖两个点，而且处于矩形边界上的点也算作被矩形覆盖。注意：矩形的长宽都必须是正整数，也就是说矩形不能退化为线段或者点。

现在的问题是：怎样选择矩形，才能够使矩形的总面积最小。
输入
输入包括多组测试数据。每组测试数据的第一行给出n (2 <= n <= 15)，表示平面上的点数。后面的n行，每行上包括两个整数x, y (-1000 <= x, y <= 1000)，给出一个点在平面上的x坐标和y坐标。输入数据保证：这n个点在平面上的位置各不相同。

最后一组测试数据中n = 0，表示输入的结束，这组数据不用处理。
输出
对每一组测试数据，输出一行，包括一个正整数，给出矩形的最小总面积。

Answer 1

类似求无向连通图的最小生成树算法；更简单，不需要矩形“连通”：
1)未覆盖的点集合为A、已覆盖点的集合为B，初始时n个点全在A中。
2)n个点两两生成最小覆盖矩形，矩形集合为R，按面积排序。
3)初始化总面积S=0
4)循环直到A为空：
4.1)从R中选最小的一个矩形r
4.2)如果r覆盖的点有不在B中的：点就从A移到B，累计面积 S=S+r
4.3)并从R中移除r。
5)输出S