【BZOJ1052】覆盖问题（贪心）

题面

BZOJ

洛谷

题解

这题好神仙啊。

很明显可以看出来要二分一个边长。

那么如何\(check\)呢？

我们把所有点用一个最小矩形覆盖，

那么必定每个边界上都至少存在一个点，

但是我们有\(4\)个边界，但是只有\(3\)个矩形，

意味着至少有一个矩形卡住了两个边界，

那么我们递归处理，每次枚举卡在了哪个角上就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 20020

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n;

struct Node{int x,y;}p[MAX];

int vis[MAX];

bool operator<(Node a,Node b)

{

	if(a.x!=b.x)return a.x<b.x;

	return a.y<b.y;

}

void cmin(int &x,int y){x=min(x,y);}

void cmax(int &x,int y){x=max(x,y);}

void Cover(int x1,int x2,int y1,int y2,int id)

{

	for(int i=1;i<=n;++i)

		if(!vis[i]&&x1<=p[i].x&&p[i].x<=x2&&y1<=p[i].y&&p[i].y<=y2)

			vis[i]=id;

}

void UnCover(int id){for(int i=1;i<=n;++i)if(vis[i]==id)vis[i]=0;}

bool dfs(int tot,int L)

{

	int x[2],y[2];x[0]=y[0]=2e9;x[1]=y[1]=-2e9;

	for(int i=1;i<=n;++i)

		if(!vis[i])cmin(x[0],p[i].x),cmax(x[1],p[i].x),cmin(y[0],p[i].y),cmax(y[1],p[i].y);

	if(max(x[1]-x[0],y[1]-y[0])<=L)return true;

	if(tot==3)return false;

	for(int i=0;i<2;++i)

		for(int j=0;j<2;++j)

		{

			if(i==0)

			{

				if(j==0)Cover(x[0],x[0]+L,y[0],y[0]+L,tot);

				else Cover(x[0],x[0]+L,y[1]-L,y[1],tot);

			}

			else

			{

				if(j==0)Cover(x[1]-L,x[1],y[0],y[0]+L,tot);

				else Cover(x[1]-L,x[1],y[1]-L,y[1],tot);

			}

			if(dfs(tot+1,L))return true;

			UnCover(tot);

		}

	return false;

}

bool check(int L)

{

	memset(vis,0,sizeof(vis));

	return dfs(1,L);

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();

	int l=0,r=2e9,ret=2e9;

	while(l<=r)

	{

		int mid=((ll)l+r)/2;

		if(check(mid))r=mid-1,ret=mid;

		else l=mid+1;

	}

	printf("%d\n",ret);

}