CF514 Div2 D - Nature Reserve

Codeforces
問題

n個の点があり、i番目の点の座標は(x[i],y[i])である
これらの点を全て内側(または境界)に含み、かつy=0と接する円を1つ描きたい
描けるならその半径の最小値を求めよ
描けない場合は-1

1 <= n <= 10^5
|x[i]|, |y[i]| <= 10^7

解法

各点のy座標の正負が全て一致していれば必ず描ける
そうでなければ描けない

半径の二分探索で解ける
半径をrと仮定すると、まず求めたい円のy座標はもちろんrになる
この円がi番目の点を内側に含むためには、この円のx座標が、「直線y=rのうち、点iを中心とした半径rの円の内側(境界含)に含まれる部分(線分)」上にある必要がある
全ての点を含むには全ての点における↑の線分の共通範囲が存在する必要がある
共通範囲が存在しなかったり、↑のような線分すら存在しない点があったら半径rでは条件を満たす円は描けない

俺は本番では↑まで辿り着けなくて、x座標を三分探索してその中で半径を二分探索する方針でやろうとした
結局誤差とか二分探索の上限ミスとかで解けなかったけど、ちゃんと書けたとしてもコドフォだとTLEしてたと思う
(計算量は5*10^8前後になる気がした)

実装

深く考えずに半径の上限を10^9にしてたんだけどそれだと足りなかった
テストケース4が (-10^7, 1) (10^7, 1) (-10^7, 10^7) (10^7, 10^7) っていう最強のケースで、これの答えが5*10^13になる

誤差がヤバイ
editorialの模範解答がlong double使ってる
あと俺は上限を10^30にしたんだけど、ここまでデカイと三平方の定理で線分の長さを求めるとき
(m*m - (y[i]-m)*(y[i]-m))
って書くとy[i]が1のときy[i]がスルーされて0になってしまう
2*y[i]*m - y[i]*y[i]
まで式展開してやったら通った
いろいろヤバイ

#define double long double

int n, fu;
double x[100100], y[100100], l = 0, r = 1e30;

bool ok(double m) {
	double lb = -1e100, rb = 1e100;
	rep(i,n) {
		if (m*2<y[i]) return 0;
		double d = sqrt(y[i]*m*2 - y[i]*y[i]);
		chmax(lb, x[i]-d), chmin(rb, x[i]+d);
	}
	return lb<=rb;
}

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> x[i] >> y[i];
		if (!fu) fu = (y[i]<0 ? -1 : 1);
		else if (fu*y[i]<0) return cout << -1 << endl, 0;
	}
	rep(i,n) y[i] *= fu;
	rep(i,200) {
		double m = (l+r)/2;
		(ok(m) ? r : l) = m;
	}
	printf("%.14Lf\n",r);
}