AtCoder ABC #181 : F - Silver Woods

こちらもすんなり思いつけた。
https://atcoder.jp/contests/abc181/tasks/abc181_f

問題

2次元座標上で、Y座標が-100～100の範囲で構成される通路がある。
ここで、(-∞,0)にある円を連続的に動かし、(∞,0)に移動したい。
途中、いくつかの座標に釘がある。

円が通路からはみ出ず、釘が円に入らないように移動できる半径の最大値を求めよ。

解法

半径Rを二分探索しよう。
通路の上端(y=100)、下端(y=-100)、各釘からなる(N+2)点において、距離が2R以下のものをUnion-Findで連結していこう。
もし上端と下端が連結した場合、経路のすべてがどこかで距離2R未満になっている箇所があるので、円が通過できない。

int N;
int X[101],Y[101];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int ok(double v) {
	UF<102> uf;
	int i,x,y;
	FOR(i,N) {
		if(Y[i]-2*v<-100) uf(100,i);
		if(Y[i]+2*v>100) uf(101,i);
	}
	FOR(x,N) FOR(y,x) if(hypot(X[y]-X[x],Y[y]-Y[x])<2*v) uf(x,y);
	
	return uf[100]!=uf[101];
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	double L=0,R=100;
	FOR(i,100) {
		double M=(L+R)/2;
		if(ok(M)) L=M;
		else R=M;
		
	}
	_P("%.12lf\n",L);
}

まとめ

問題タイトルはどういう意味なんだろう。