[poj2296]Map Labeler(二分答案 + 2-SAT)

由于每个点只可能位于正方形上边中点或下边中点，考虑2-SAT。我们可以按纵坐标升序给点排个序。若已知正方形边长为x，首先如果两个点横坐标差大于x，那么无论如何也不会覆盖。否则，计算两点纵坐标之差：1.为0，则必一上一下  2.大于0且小于x，则只能前一个点向下盖，后一个点向上盖  3.大于x小于2*x，则前一个点向上盖时，后一个必向上；后一个向下时，前一个必向下

点的个数不多，二分法每次验证一个值可不可行时通过枚举点对重建一次图。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210,M=40010;
struct node{
	int x,y;
}p1[N>>1];
struct edge{
	int y,next;
}data[M];
int t,n,nn,num,num1,num2,top,l,r,mid,h[N],dfn[N],low[N],sta[N],f[N];
bool insta[N],flag;
inline int read(){
	int x=0,f=0;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 f?-x:x;
}
inline bool cmp1(node i,node j){return i.y<j.y;}
inline void add(int u,int v){
	data[++num].y=v,data[num].next=h[u],h[u]=num;
}
void tarjan(int u){
	dfn[u]=low[u]=++num1,insta[u]=true,sta[++top]=u;
	for(int i=h[u],v;i!=-1;i=data[i].next){
		v=data[i].y;
		if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
		else if(insta[v]&&low[u]>dfn[v])low[u]=dfn[v];
	}
	if(dfn[u]==low[u]){
		++num2;
		while(dfn[sta[top]]!=low[sta[top]])
			insta[sta[top]]=false,f[sta[top]]=num2,top--;
		insta[u]=false,f[u]=num2,top--;
	}
}
inline bool two_sat(int x){
	num=num1=num2=top=0;memset(h,-1,sizeof h);
	for(int i=2;i<=n;++i)
		for(int j=1,del;j<i;++j){
			del=abs(p1[i].x-p1[j].x);
			if(del>=x)continue;
			if(p1[i].y==p1[j].y)add(i<<1,j<<1|1),add(i<<1|1,j<<1),add(j<<1,i<<1|1),add(j<<1|1,i<<1);
			else if(p1[i].y-p1[j].y<x)add(i<<1,j<<1|1),add(i<<1|1,i<<1),add(j<<1,j<<1|1),add(j<<1|1,i<<1);
			else if(p1[i].y-p1[j].y<(x<<1))add(i<<1|1,j<<1|1),add(j<<1,i<<1);
		}
	memset(dfn,0,sizeof dfn);flag=true;
	for(int i=2;i<=nn;++i)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;++i)if(f[i<<1]==f[i<<1|1])flag=false;
	return flag;
}
int main(){
	t=read();
	while(t--){
		n=read();nn=n<<1|1;
		for(int i=1;i<=n;++i)p1[i].x=read(),p1[i].y=read();
		sort(p1+1,p1+n+1,cmp1);
		l=1,r=40000;
		while(l<=r){
			mid=(l+r)>>1;
			if(two_sat(mid))l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",r);
	}
	return 0;
}