Codeforces #514 Div2 D. Nature Reserve

悪くはない結果でした。
http://codeforces.com/contest/1059/problem/D

問題

２次元座標上でいくつかの点が与えられる。
y=0と接する円のうち、全点を円周上または内部に含む円の半径の最小値を求めよ。

解法

まず全点のy座標の正負が一致していることを確認しよう。
あとはここから以下どちらのアプローチでもよい。

• 半径の最小値を二分探索する。
  • 半径を定めると円の中心のy座標も定まるので、各点に対し円の中心の存在可能なX座標の区間を求めよう。全区間に共通部分があるような半径の最小値を求めればよい。
• 半径が最小となる中心のX座標を三分探索する。
  • 中心のX座標を定めると、各点を含むための半径およびY座標の最小値が求まる。よってX座標を三分探索して半径が最小となるタイミングを求めよう。

以下のコードは前者。
X座標の範囲を求める際、小数の誤差に注意すること。
三平方の定理のためにうかつに半径の二乗を取ると大変。

int N;
ll X[101010],Y[101010];

int ok(long double M) {
	long double L=-3e20,R=3e20;
	int i;
	FOR(i,N) {
		if(2*M<Y[i]) return 0;
		long double dx=sqrt(Y[i]*(2*M-Y[i]));
		L=max(L,X[i]-dx);
		R=min(R,X[i]+dx);
	}
	return L<=R;
	
	
}

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

まとめ

割とシンプルに解けたとは思う。