首页 > 代码库 > BZOJ 1052 HAOI2007 覆盖问题 二分答案+DFS
BZOJ 1052 HAOI2007 覆盖问题 二分答案+DFS
题目大意:给定n个点,用三个边长相同的正方形覆盖所有点,要求正方形边界与坐标轴垂直,求正方形边长的最小值
最大值最小,很明显二分答案
但是验证是个问题
考虑只有三个正方形,故用一个最小矩形覆盖这三个正方形时至少有一个在角上 若有四个正方形该结论不成立
于是我们采用DFS的方式 每次用一个最小的矩形覆盖所有的点,枚举矩形的四个角 将正方形填进去
由于最大深度是3,所以时间上完全可以承受
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 20100 using namespace std; struct abcd{ int x,y; }points[M]; int n,v[M]; int stack[M],top; bool DFS(int L,int dpt) { int i,j,bottom=top; int minx=0x3f3f3f3f,maxx=0xefefefef; int miny=0x3f3f3f3f,maxy=0xefefefef; if(top==n) return true; if(dpt==3) return false; for(i=1;i<=n;i++) if(!v[i]) { minx=min(minx,points[i].x); maxx=max(maxx,points[i].x); miny=min(miny,points[i].y); maxy=max(maxy,points[i].y); } int dx[]={minx,minx,maxx-L,maxx-L}; int dy[]={miny,maxy-L,miny,maxy-L}; for(j=0;j<4;j++) { for(i=1;i<=n;i++) if(!v[i]) if(points[i].x>=dx[j]&&points[i].x<=dx[j]+L) if(points[i].y>=dy[j]&&points[i].y<=dy[j]+L) v[i]=1,stack[++top]=i; bool flag=DFS(L,dpt+1); while(top!=bottom) v[stack[top--]]=0; if(flag) return true; } return false; } int Bisection() { int l=0,r=0x3f3f3f3f; while(l+1<r) { int mid=l+r>>1; if( DFS(mid,0) ) r=mid; else l=mid; } if( DFS(l,0) ) return l; return r; } int main() { int i; cin>>n; for(i=1;i<=n;i++) scanf("%d%d",&points[i].x,&points[i].y); cout<<Bisection()<<endl; }
BZOJ 1052 HAOI2007 覆盖问题 二分答案+DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。