BOJ 9200 Anchored Balloon

문제 링크입니다.

문제 요약

$N$개의 줄로 묶여 있는 풍선이 떠오를 수 있는 최대 높이를 구하세요. 답은 0 이상임이 보장됩니다.

볼록성

xy평면 상에서 풍선의 위치가 $(x, y)$라면 풍선의 높이의 제곱은 $\min { R^2 - (\Delta x)^2 - (\Delta y) ^2 }$입니다. $R$은 줄의 길이, $\Delta x$는 줄의 고정점과 풍선의 $x$좌표 차이, $\Delta y$는 $y$좌표 차이입니다. 이 정의대로면 상황에 따라 음수가 나올 수 있는데, 일단 그런 셈 치고 넘어갑시다.

각 줄마다, $x$좌표가 고정되어 있을 때의 $y$좌표에 따른 풍선 높이의 제곱 값은 위로 볼록한 함수가 됩니다. 위로 볼록한 함수들의 $\min$ 역시 위로 볼록한 함수이므로, 고정된 $x$좌표에 대한 답을 삼분 탐색으로 구할 수 있습니다.

같은 이유로 이 함수는 $x$좌표에 대해서도 위로 볼록한 함수입니다. 그러니 $x$좌표에 대한 삼분 탐색 안에서 $y$좌표에 대한 삼분 탐색을 돌리면 답을 얻을 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
const ld EPS = 1e-12;

int X[15], Y[15], R[15];
int n;

ld solve(ld x, ld y){
	ld ret = R[1]*R[1];
	for(int i = 1; i <= n; i++) ret = min(ret, R[i]*R[i]-(x-X[i])*(x-X[i])-(y-Y[i])*(y-Y[i]));
	return ret;
}

ld solve(ld x){
	ld l = -100, r = 100;
	while(r-l>EPS){
		ld m1 = (l+l+r)/3; ld m2 = (l+r+r)/3;
		if(solve(x, m1) < solve(x, m2)) l = m1;
		else r = m2;		
	}
	return solve(x, l);
}

ld solve(){
	ld l = -100, r = 100;
	while(r-l>EPS){
		ld m1 = (l+l+r)/3; ld m2 = (l+r+r)/3;
		if(solve(m1) < solve(m2)) l = m1;
		else r = m2;
	}
	return solve(l);
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	while(1){
		cin >> n; if(!n) return 0;
		for(int i = 1; i <= n; i++) cin >> X[i] >> Y[i] >> R[i];
		cout << fixed << setprecision(12) << sqrt(solve()) << '\n';
	}
}