一、题目大意
坐标系中有n个点，它们满足 -1000<=x<=1000,-1000<=y<=1000。
现在要在坐标系中放一些矩形，要使得每个点都被矩形覆盖（被矩形的边或者顶点覆盖也可以），每个矩形都必须满足面积大于0，且每个矩形最少要覆盖两个点。
请你输出覆盖所有点时，如何使所有矩形的面积和最小，输出这个面积和。
二、解题思路
我们可以从左上角的点开始，一点点的覆盖到右下角的点。
那么对于第 i 个点，我们可以认为
1、i 以前的点都被覆盖；
2、如果 i 还未被覆盖，则它必须被覆盖。
同时思考下，当铺设到第 i 个点时，对于覆盖情况固定时，铺完剩下的点需要的最小矩形面积是固定的。
则可以定义DP数组，DP[S][i]代表已经铺设的点的集合为S时，铺设好第 i 个点到最后一个点所需要的最小的矩形面积。
对于最后一个点n-1，如果S包含n-1，则DP[S][n-1]=0，如果不包含，那么DP[S][n-1]=点n-1到其余点的矩形的面积的最小值。
那么借助这个思路，我们就可以展开循环，外层放 i ，从 n - 1 到 0循环，内层放 S，从 1 到 (1<<n)-1循环，当S包含 i 时，则DP[S][i]=DP[S][i+1]。
如果S不包含 i ，就循环其他所有点 j (i != j），
DP[S][i]=min(DP[S][i],DP[S 添加 i 添加 j][i+1]+i和j组成的矩形面积）
思路可以了，但欠缺一点，有时候一个矩形会覆盖两个点。
这种情况仅在两个点同行或同列的情况出现，否则是下图
那么加个判断，如果两个点是同一条直线，它们之间的矩形为零的那条边设置长度为1。同时连一条边的时候，判断是否有其他点是否也在矩形内的，记录它们到集合child里，更改递推式为
DP[S][i]=min(DP[S][i],DP[S 添加 i 添加 j 添加child内所有的元素][i+1]+i和j组成的矩形面积）
（这里只判断 i 之后的点是否在范围内即可，因为之前的不会影响到DP[XXX][i+1]之后的值）
循环集合时，要跳过确定已经连了的部分来提速。
三、代码
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct P
{
int x, y;
P(int x = 0, int y = 0) : x(x), y(y) {}
};
bool compare(P &a, P &b)
{
return a.y != b.y ? a.y > b.y : a.x < b.x;
}
const int MAX_N = 15;
const int INF = 0x3f3f3f3f;
int dp[2][1 << MAX_N];
P dat[15];
int n;
int *crt = dp[0], *nxt = dp[1];
void solveItem(int i, int used)
{
if (used >> i & 1)
{
nxt[used] = crt[used];
return;
}
nxt[used] = INF;
for (int j = 0; j < n; j++)
{
if (i == j)
{
continue;
}
int w = abs(dat[i].x - dat[j].x);
int h = abs(dat[i].y - dat[j].y);
int x1 = min(dat[i].x, dat[j].x);
int y1 = min(dat[i].y, dat[j].y);
int area = (w > 0 ? w : 1) * (h > 0 ? h : 1);
int child = 0;
for (int k = i + 1; k < n; k++)
{
if ((dat[k].x >= x1 && dat[k].x <= (x1 + w) && dat[k].y >= y1 && dat[k].y <= (y1 + h)) ||
(w == 0 && dat[k].x >= (x1 - 1) && dat[k].x <= x1 && dat[k].y >= y1 && dat[k].y <= (y1 + h)) ||
(h == 0 && dat[k].y >= (y1 - 1) && dat[k].y <= y1 && dat[k].x >= x1 && dat[k].x <= (x1 + w)))
{
child = child | (1 << k);
}
}
nxt[used] = min(nxt[used], crt[used | (1 << i) | (1 << j) | child] + area);
}
}
void solve()
{
memset(dp, 0, sizeof(dp));
int all = (1 << n) - 1;
for (int i = n - 1; i >= 0; i--)
{
all = all & ~(1 << i);
for (int S = 0; S < (1 << (n - i)); S++)
{
int used = all | (S << i);
solveItem(i, used);
}
swap(crt, nxt);
}
printf("%d\n", crt[0]);
}
int main()
{
while (true)
{
scanf("%d", &n);
if (n == 0)
{
break;
}
for (int i = 0; i < n; i++)
{
scanf("%d%d", &dat[i].x, &dat[i].y);
}
sort(dat, dat + n, compare);
solve();
}
return 0;
}
