描述
在平面上有 n 个点（n <= 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7）。
这些点可以用 k 个矩形（1<=k<=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 s1，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。
格式
输入格式
格式为
n k
xl y1
x2 y2
... ...
xn yn （0<=xi,yi<=500)
输出格式
一个整数，即满足条件的最小的矩形面积之和。
样例1
样例输入1
4 2
1 1
2 2
3 6
0 7
1 1
2 2
3 6
0 7
样例输出1
4
题解
看着数据范围就是搜索了，这道题我用了三个剪枝（如果能算剪枝的话）。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=1<<30;
struct dian {int x,y;} a[52];
struct jux{int xz,xy,ys,yx,tag;} b[5];
void init()
{
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
}
bool jiao(jux i,int x,int y)
{
if(x>=i.xz&&x<=i.xy&&y<=i.ys&&y>=i.yx) return true;
else return false;
}
bool check(jux i,jux j)
{
if(jiao(j,i.xz,i.yx)) return true;
if(jiao(j,i.xy,i.yx)) return true;
if(jiao(j,i.xz,i.ys)) return true;
if(jiao(j,i.xy,i.ys)) return true;
return false;
}
void dfs(int x)
{
int i,j,s=0;
for(i=1;i<=m;i++)//1、判断矩形是否重合
{if(b[i].tag)
{s+=(b[i].xy-b[i].xz)*(b[i].ys-b[i].yx);
for(j=i+1;j<=m;j++)//节省时间
{if(b[j].tag&&check(b[i],b[j])) return;}
}
}
if(s>=ans) return; //2、一种常用剪枝
if(x>n) {ans=s; return;}
jux t;
for(i=1;i<=m;i++)
{t=b[i];
if(!b[i].tag)
{b[i].xz=a[x].x; b[i].xy=a[x].x; b[i].ys=a[x].y; b[i].yx=a[x].y;
b[i].tag=1;
}
else
{b[i].xz=min(a[x].x,b[i].xz); b[i].xy=max(b[i].xy,a[x].x);
b[i].ys=max(b[i].ys,a[x].y); b[i].yx=min(b[i].yx,a[x].y);
}
dfs(x+1);
b[i]=t;
if(!t.tag) return;//3、保证每个矩形都用上
}
}
int main()
{
init(); dfs(1);
printf("%d\n",ans);
return 0;
}