题面
在平面上有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覆盖，81，S2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢？
约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。题意
有n个点，找k个矩形包含所有点，使k个矩形和面积和最小。
题解
这道题刚拿到手里的时候是挺棘手的，但是我们看数据范围的大小，是可以暴力枚举的，所以我们可以尝试一下暴力枚举。
建图操作
maps用来存图
ss用来存构建的矩形
立flag来统计这种矩形是否建过
数据最大是4块矩形，可以开小数组
struct maps{ int x,y;} mapp[51];struct ss{ int l,r,u,d; bool flag;} p[5]; 判断操作
judge函数枚举四种不成立的情况
in函数判断范围，便于书写judge函数
bool in(ss a, int x, int y){ if (x>=a.l&&x<=a.r&&y>=a.d&&y<=a.u) return 1; return 0;}bool judge(ss a, ss 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;} dfs操作
构建好m个矩形
计算面积和
每次存最小值
搜完结束
void dfs(int num){ int value=0; for (int i=1; i<=m; i++) { if (p[i].flag) { for (int j=i+1; j<=m; j++) 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 (int i=1; i<=m; i++) { ss tmp=p[i]; if (p[i].flag==0) { p[i].flag=1; p[i].l=p[i].r=mapp[num].x; p[i].u=p[i].d=mapp[num].y; dfs(num+1); p[i]=tmp; break; } else { p[i].r=max(p[i].r,mapp[num].x); p[i].l=min(p[i].l,mapp[num].x); p[i].u=max(p[i].u,mapp[num].y); p[i].d=min(p[i].d,mapp[num].y); dfs(num+1); p[i]=tmp; } }} 代码
#include#include using namespace std;struct maps{ int x,y;} mapp[51];struct ss{ int l,r,u,d; bool flag;} p[5];int n,m,ans=0x7f7f7f7f;bool in(ss a, int x, int y){ if (x>=a.l&&x<=a.r&&y>=a.d&&y<=a.u) return 1; return 0;}bool judge(ss a, ss 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;}void dfs(int num){ int value=0; for (int i=1; i<=m; i++) { if (p[i].flag) { for (int j=i+1; j<=m; j++) 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 (int i=1; i<=m; i++) { ss tmp=p[i]; if (p[i].flag==0) { p[i].flag=1; p[i].l=p[i].r=mapp[num].x; p[i].u=p[i].d=mapp[num].y; dfs(num+1); p[i]=tmp; break; } else { p[i].r=max(p[i].r,mapp[num].x); p[i].l=min(p[i].l,mapp[num].x); p[i].u=max(p[i].u,mapp[num].y); p[i].d=min(p[i].d,mapp[num].y); dfs(num+1); p[i]=tmp; } }}int main(void){ scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) scanf("%d%d",&mapp[i].x,&mapp[i].y); dfs(1); printf("%d",ans); return 0;}