2002NOIPTG 矩形覆盖搜索

题目描述 在平面上有n个点(n≤50)，每个点用一对整数坐标表示。例如：当n=4 时，4个点的坐标分另为：p_1 (1,1)，p_2 (2,2)，p_3(3,6)，P_4(0,7)，见图一。

这些点可以用k个矩形(1≤k≤4)全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 s_1,s_2覆盖，s_1,s_2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢？ 约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。

输入格式 n k x_1 y_1 x_2 y_2 … …

x_n y_n 输出格式 输出至屏幕。

格式为：

1个整数，即满足条件的最小的矩形面积之和。

输入输出样例 输入 #1 4 2 1 1 2 2 3 6 0 7 输出 #1 4

解法：搜索

我们搜索每一个点，枚举放到哪个矩形，判断矩形之间是否有包含，如果有直接返回加上最优化剪枝，如果超过答案就直接返回，回溯时需要回溯完全

AC代码

#include<cstdio> #define re register int using namespace std; struct node { int x,y; }e[505]; struct rec {//矩形 int l,r,u,d; bool flag; }p[5]; int n,k,ans=0x3f3f3f3f; inline int min(int A,int B) { return A<B?A:B; } inline int max(int A,int B) { return A>B?A:B; } inline bool in(rec a,int x,int y) { if(x>=a.l&&x<=a.r&&y>=a.d&&y<=a.u) return 1;//判断是否包含 return 0; } inline bool judge(rec a,rec b) {//直接判断四个顶点是否在范围内 if(in(a,b.l,b.u)) return 1; if(in(a,b.l,b.d)) return 1; if(in(a,b.r,b.u)) return 1; if(in(a,b.r,b.d)) return 1; return 0; } inline void dfs(int num) { int value=0; for(re i=1;i<=k;i++) { if(p[i].flag) { for(re j=i+1;j<=k;j++) { if(!p[j].flag) continue; if(judge(p[i],p[j])) return; } } value+=(p[i].r-p[i].l)*(p[i].u-p[i].d); } if(value>ans) return;//最优性剪枝 if(num>n) { ans=value; return; } for(re i=1;i<=k;i++) { rec tmp=p[i]; if(!p[i].flag) { p[i].flag=1; p[i].l=p[i].r=e[num].x; p[i].u=p[i].d=e[num].y; dfs(num+1); p[i]=tmp; break; } else { p[i].l=min(p[i].l,e[num].x); p[i].r=max(p[i].r,e[num].x); p[i].u=max(p[i].u,e[num].y); p[i].d=min(p[i].d,e[num].y); dfs(num+1); p[i]=tmp; } } } int main() { scanf("%d%d",&n,&k); for(re i=1;i<=n;i++) { scanf("%d%d",&e[i].x,&e[i].y); } dfs(1); printf("%d",ans); return 0; }