New Year Contest 2015 : H - 空港

こちらも本番に何とかひらめいた感じ。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_8

問題

２次元座標上でN個の空港の位置が与えられる。
これらの空港のうち、互いの距離がx以上である空港ペア間で飛行機を飛ばすことにした。

全都市間を飛行機で移動できるようになる最小のxを求めよ。

解法

二分探索で求める。
まず事前に全空港をX座標順およびY座標順にソートしておく。
xに対し、以下のようにUnion-Findを行う。

• 一番X座標が小さい空港とX座標がx以上差がある空港をuniteする。
• 一番X座標が大きい空港と（以下同様）
• 一番Y座標が小さい空港とY座標がx以上差がある空港をuniteする。
• 一番Y座標が大きい空港と（以下同様）

上記処理で全空港をunite出来てるなら、xは解の候補となる。

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N;
ll X[101000],Y[101000];
pair<ll,int> P[101000];

ll ok(ll val) {
	UF uf;
	int i;
	
	FOR(i,N) P[i]=make_pair(X[i],i);
	sort(P,P+N);
	for(i=N-1;i>=0;i--) {
		if(P[i].first-P[0].first<val) break;
		uf.unite(P[0].second,P[i].second);
	}
	FOR(i,N) {
		if(P[N-1].first-P[i].first<val) break;
		uf.unite(P[N-1].second,P[i].second);
	}
	FOR(i,N) P[i]=make_pair(Y[i],i);
	sort(P,P+N);
	for(i=N-1;i>=0;i--) {
		if(P[i].first-P[0].first<val) break;
		uf.unite(P[0].second,P[i].second);
	}
	FOR(i,N) {
		if(P[N-1].first-P[i].first<val) break;
		uf.unite(P[N-1].second,P[i].second);
	}
	int cnt=0;
	FOR(i,N) if(uf[i]==i) cnt++;
	return cnt==1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		X[i]=x+y;
		Y[i]=x-y;
	}
	ll ret=0;
	for(i=30;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

これは割と綺麗に解けたかな。