BZOJ 1052 HAOI2007 覆蓋問題 二分答案+DFS

BZOJ 1052 HAOI2007 覆蓋問題 二分答案+DFS

題目大意：給定n個點，用三個邊長相同的正方形覆蓋所有點，要求正方形邊界與坐標軸垂直，求正方形邊長的最小值

最大值最小，很明顯二分答案

但是驗證是個問題

考慮只有三個正方形，故用一個最小矩形覆蓋這三個正方形時至少有一個在角上 若有四個正方形該結論不成立

於是我們采用DFS的方式 每次用一個最小的矩形覆蓋所有的點，枚舉矩形的四個角 將正方形填進去

由於最大深度是3，所以時間上完全可以承受

#include
#include
#include
#include
#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>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<