题目是平面上n个点，要用若干个矩形盖住它们，每个矩形上至少要包含2个点，问要用的矩形的面积和最少是多少。
容易反证得出每个矩形上四个角必定至少覆盖了两个点。然后就状压DP：
- dp[S]表示覆盖的点集为S要用的最少矩形面积
转移我一开始是未覆盖的点和已覆盖的点构成一个矩形来转移，这是错的，因为这样子的结果是所有矩形都相连的最小面积和。
正确的是枚举还未被覆盖的矩形来转移。转移我用我为人人+队列。
有一点要注意的是，覆盖(0,0)和(0,2)两点要用的矩形是1*2，所以要特判一下两点斜率0或不存在时构成的矩形。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<29) bool isIn(int x1,int y1,int x2,int y2,int x,int y){
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
return x1<=x && x<=x2 && y1<=y && y<=y2;
}
int area(int x1,int y1,int x2,int y2){
if(x1==x2) ++x2;
if(y1==y2) ++y2;
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
return (x2-x1)*(y2-y1);
}
int d[<<],sta[][];
bool inque[<<];
int main(){
int n,x[],y[];
while(~scanf("%d",&n) && n){
for(int i=; i<n; ++i) scanf("%d%d",x+i,y+i);
for(int i=; i<(<<n); ++i) d[i]=INF;
queue<int> que;
memset(inque,,sizeof(inque));
for(int i=; i<n; ++i){
for(int j=i+; j<n; ++j){
int s=;
for(int k=; k<n; ++k){
if(isIn(x[i],y[i],x[j],y[j],x[k],y[k])) s|=(<<k);
}
sta[i][j]=sta[j][i]=s;
if(d[s]>area(x[i],y[i],x[j],y[j])){
d[s]=area(x[i],y[i],x[j],y[j]);
if(!inque[s|sta[i][j]]){
inque[s]=;
que.push(s);
}
}
}
}
while(!que.empty()){
int s=que.front(); que.pop();
for(int i=; i<n; ++i){
for(int j=i+; j<n; ++j){
if(((s>>i)&) && ((s>>j)&)) continue;
if(d[s|sta[i][j]]>d[s]+area(x[i],y[i],x[j],y[j])){
d[s|sta[i][j]]=d[s]+area(x[i],y[i],x[j],y[j]);
if(!inque[s|sta[i][j]]){
inque[s|sta[i][j]]=;
que.push(s|sta[i][j]);
}
}
}
}
inque[s]=;
}
printf("%d\n",d[(<<n)-]);
}
return ;
}