POJ Map Labeler（2-Sat）

• Map Labeler

• 题意

  有一些点，现在要对每个点构建一个正方形，这个点可以作为此正方形的上边界的中点或者是下边界的中点，对每个点构建的正方形的边长是相等的，要求构建的这些正方形不可以重叠，但是边界可以重叠，求可以构建的正方形的最大边长是多少？

• 题解

  对于一个点，要么向上构建正方形，要么向下构建正方形，只有两种情况，二分答案，用2-Sat判断是否满足。2-Sat最关键的也是最难的就是建图了：

  对于点i,x是向上构建，x^1是向下构建。点j对于y雷同，尝试当前边长m

  1.如果abs(Xi-Xj)>=m或者abs(Yi-Yj)>=2*m,continue

  2.如果Yi==Yj,add(x,y^1),(x^1,y);

  3.如果abs(Yi-Yj)>=m,Yi>Yj?add(x^1,y^1):add(x,y);

  4.如果abs(Yi-Yj)<m,Yi>Yj?add(x^1,x):add(x,x^1);这种情况我们知道i，j的构建方向已经确定了，也就是只有一种情况，这时候加边的目的就是确定这种唯一的情况。

• 代码

#pragma GCC optimize(2)
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>

using namespace std;

typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair<ll,ll> pa;
const int dir_4[4][2]={-1,0,0,1,1,0,0,-1};
const int dir_8[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAX_N=500; 
int T,N,dfn[MAX_N],low[MAX_N],sccnum[MAX_N],head[MAX_N],scc_cnt,cnt,tot;
struct Pos{
	int x,y;
	Pos(){}
	Pos(int x,int y):x(x),y(y){}
}pos[MAX_N];
struct Edge{
	int to,nex;
}edge[1000000];
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].nex=head[u];
	head[u]=cnt++;
	return ;
}
stack<int>st;
void Init(){
	cnt=tot=scc_cnt=0;
	for(int i=0;i<(N<<1);i++){
		head[i]=-1;
		dfn[i]=sccnum[i]=0;
	}
	while(!st.empty())
	st.pop();
	return ;
}
void Tarjan(int u){
	dfn[u]=low[u]=++tot;
	st.push(u);
	int i,j,v;
	for(i=head[u];~i;i=edge[i].nex){
		v=edge[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccnum[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++scc_cnt;
		while(!st.empty()){
			v=st.top();
			st.pop();
			sccnum[v]=scc_cnt;
			if(v==u)
			break;
		}
	}
	return ;
}
void built_map(int m){
	int i,j,k;
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			int x=i<<1;//定位到i的两个bool值 
			int y=j<<1;//定位到j的两个bool值 
			if(i==j)
			continue;
			if(abs(pos[i].x-pos[j].x)>=m||abs(pos[i].y-pos[j].y)>=2*m)//两个城市标签摆放没有关系 
			continue;
			if(pos[i].y==pos[j].y){
				add(x,y^1);
				add(x^1,y);
			}
			else if(abs(pos[i].y-pos[j].y)>=m){
				pos[i].y>pos[j].y?add(x^1,y^1):add(x,y);
			}
			else{
				pos[i].y>pos[j].y?add(x^1,x):add(x,x^1);
			}
		}
	}
	return ;
}
bool is_ok(int m){
	int i,j,k;
	Init();
	built_map(m);
	for(i=0;i<(N<<1);i++){
		if(!dfn[i])
		Tarjan(i);
	}
	for(i=0;i<(N<<1);i+=2){
		if(sccnum[i]==sccnum[i^1])
		return false;
	}
	return true;
}
int main()
{
//  freopen(".../.txt","w",stdout);
//  freopen(".../.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int i,j,k;
	int x,y;
	scf("%d",&T);
	while(T--){
		scf("%d",&N);
		for(i=0;i<N;i++){
			scf("%d %d",&x,&y);
			pos[i]=Pos(x,y);
		}
		int l=0,r=20000,mid,res=-1;
		while(l<=r){
			mid=(l+r)>>1;
			if(is_ok(mid)){
				res=mid;
				l=mid+1;	
			}
			else
			r=mid-1;
		}
		prf("%d\n",res);
	}
	return 0;
}