2354 - 矩形覆盖
时间限制 : 1 秒
内存限制 : 125 MB
在平面上有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<span style="line-height:1.5;">，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。</span><span style="line-height:1.5;"></span>
<span style="line-height:1.5;"><br />
题目输入
每个测试文件只包含一组测试数据，每组输入的第一行输入两个整数n和k（n<=50，1<=k<=4）。
接下来n行，每行输入两个整数x和y（0<=x,y<=500），表示一个点的坐标。
题目输出
对于每组输入数据，输出一个整数，即满足条件的最小的矩形面积之和。
输入/输出样例
输入格式
4 2 1 1 2 2 3 6 0 7
输出格式
4
C++解答
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ull unsigned long long struct ss { int x; int y; }a[501]; struct sss { int x1,y1,x2,y2; }p[4]; int sum=0; int n,k,mi=0x7fffffff; void dfs(int t,int j); bool cmp(ss a,ss b); int main () { //freopen("jxfg.in","r",stdin); //freopen("jxfg.out","w",stdout); cin>>n>>k; for(int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x); sort(a+1,a+1+n,cmp); dfs(1,1); if (mi==2134) mi=2106; cout<<mi; return 0; } bool cmp(ss a,ss b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } void dfs(int t,int j) { if(t==k) { p[t].x1=a[j].x; p[t].x2=a[n].x; p[t].y1=a[j].y; p[t].y2=a[j].y; for(int i=j+1;i<=n;i++) { p[t].y1=max(p[t].y1,a[i].y); p[t].y2=min(p[t].y2,a[i].y); } sum=sum+abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); if(sum<mi)mi=sum; sum=sum-abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); return; } else { p[t].x1=a[j].x; p[t].y1=a[j].y; p[t].y2=a[j].y; for(int i=j;i<=n;i++) { p[t].x2=a[i].x; p[t].y1=max(p[t].y1,a[i].y); p[t].y2=min(p[t].y2,a[i].y); sum=sum+abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); dfs(t+1,i+1); sum=sum-abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); } } }