水晶之恋天生一对,王静kiko,2017年第2号台风
在平面上有n个点(n<=50),每个点用一对整数坐标表示。例如:当n=4时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),p4(0,7),见图一。
这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。
n k
xl y1
x2 y2
… …
xn yn
(0<=xi,yi<=500)
输出至屏幕。格式为:
一个整数,即满足条件的最小的矩形面积之和。
4 2 1 1 2 2 3 6 0 7
4
主要是搜索。
这题剪枝方法似乎多种多样。
下面将要展示代码的做法:
将读入的坐标按x和y从小到大排序,然后搜索将连续的i个点分在一起,期间判断问题是否可行,以及进行各种小优化。
code
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct point{ int x,y; }a[60]; int cmp(point a,point b){ if(a.x==b.x)return a.y<b.y; return a.x<b.x; } struct block{ int x1,y1,x2,y2; }b[5]; int n,k; int ans=1e9; void dfs(int pos,int cnt,int smm){ if(pos>n){ ans=min(ans,smm); return; } if(cnt>k)return; int i,j; b[cnt].x1=a[pos].x; b[cnt].x2=a[pos].x; b[cnt].y1=a[pos].y; b[cnt].y2=a[pos].y; for(i=pos;i<=n;i++){ b[cnt].y2=max(b[cnt].y2,a[i].y); b[cnt].x2=max(b[cnt].x2,a[i].x); b[cnt].x1=min(b[cnt].x1,a[i].x); b[cnt].y1=min(b[cnt].y1,a[i].y); for(j=1;j<cnt;j++){ if(b[cnt].x1<=b[j].x2 && b[cnt].y1<=b[j].y2)return; } if(i<n && cnt==k)continue; dfs(i+1,cnt+1,smm+(b[cnt].x2-b[cnt].x1)*(b[cnt].y2-b[cnt].y1)); } return; } int main(){ n=read();k=read(); int i,j; for(i=1;i<=n;i++){ a[i].y=read();a[i].x=read(); } sort(a+1,a+n+1,cmp); memset(b,-1,sizeof b); dfs(1,1,0); printf("%d\n",ans); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论