标题效果：特定n点。涵盖所有的点与同方三面。斧头要求方垂直边界，最小平方的需求方长值

最大值至少。答案是很明显的二分法

但验证是一个问题

考虑仅仅有三个正方形，故用一个最小矩形覆盖这三个正方形时至少有一个在角上 若有四个正方形该结论不成立

于是我们採用DFS的方式 每次用一个最小的矩形覆盖全部的点，枚举矩形的四个角 将正方形填进去

因为最大深度是3，所以时间上全然能够承受

#include
     
      #include
      
       #include
       
        #include
        
         #define M 20100using 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
         
          >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<
          
           <
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。