TopCoder SRM 464 Div1 Medium ColorfulDecoration

問題

同じ大きさをしたn個の正方形を座標平面上に、軸に平行に、かつ重ならないように置きたい。
それぞれの正方形の中心の座標は(xa[i],ya[i])または(xb[i],yb[i])のどちらかでなければならない。

正方形の一辺の長さの最大値を求めよ。

制約条件

n≦50
座標の絶対値≦10^9

方針

2-SAT + 二分探索。
正方形の一辺をひとつ決めたときに、
干渉しあう正方形同士の関係がグラフに出来る。
たとえばi番目の正方形をaから選んだときとj番目の正方形をaから選んだときに干渉するとき、
i⇒¬j∧j⇒¬iが成り立つ。

これを2-SATとして解けば、干渉しあわないような正方形の置き方が存在するかどうかがわかる。

ソースコード

const int MAX_V=100;
int V;
vi G[MAX_V], rG[MAX_V];
vi vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from,int to){
	G[from].pb(to);
	rG[to].pb(from);
}
void dfs(int v){
	used[v]=1;
	rep(i,G[v].size())if(!used[G[v][i]])dfs(G[v][i]);
	vs.pb(v);
}
void rdfs(int v,int k){
	used[v]=1;
	cmp[v]=k;
	rep(i,rG[v].size())if(!used[rG[v][i]])rdfs(rG[v][i],k);
}
int scc(){
	memset(used,0,sizeof(used));
	vs.clear();
	rep(v,V)if(!used[v])dfs(v);
	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--)if(!used[vs[i]])rdfs(vs[i],k++);
	return k;
}

class ColorfulDecoration {
	public:
	int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb) 
	{
		int n=xa.size();
		xa.insert(xa.end(),all(xb));
		ya.insert(ya.end(),all(yb));
		
		V=2*n;
		ll lo=-1,hi=10000000000ll,mid;
		while(lo+1<hi){
			mid=(lo+hi)/2;
			rep(i,V)G[i].clear(), rG[i].clear();
			#define NOT(x) (x<n?x+n:x-n)
			rep(i,V)rep(j,i)if(max(abs(xa[i]-xa[j]),abs(ya[i]-ya[j]))<mid)
				add_edge(i,NOT(j)), add_edge(j,NOT(i));
			scc();
			bool ok=1;
			rep(i,n)ok&=cmp[i]!=cmp[NOT(i)];
			if(ok)lo=mid; else hi=mid;
		}
		return lo;
	}
};