AOJ 1190 Anchored Balloon (ICPC国内予選2013問題E)

• 問題文

一つの杭と紐に注目したときに風船が動ける空間は球になっています。(正確にはz<0の空間には移動できないので球を半分にしたような空間ですが)

n個の杭と紐につながった風船が動ける空間はそれぞれの杭と紐について注目した時に動ける空間の共通部分となっていて、その形は凸になっています。(球は凸集合で、凸集合と凸集合の共通部分も凸集合です)

なのでxについて三分探索し, そのなかでyについて三分探索することで最大の高さを求めることができます。(x,yが決まるとその位置について風船が動ける最大の高さを計算できます)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
double x[10], y[10], l[10];

double search(double X, double Y){
    double res = 1e+9;
    for(int i = 0; i < n; i++){
        double h = l[i] * l[i] - ((X - x[i]) * (X - x[i])) - ((Y - y[i]) * (Y - y[i]));
        res = min(res, h);
    }
    return res;
}

double searchY(double X){
    double left = -100.0, right = 100.0;
    for(int i = 0; i < 200; i++){
        double mid1 = (2 * left + right) / 3;
        double mid2 = (left + 2 * right) / 3;
        if( search(X, mid1) > search(X, mid2) ){
            right = mid2;
        }else{
            left = mid1;
        }
    }
    return search(X, left);
}

double searchXY(double left = -100.0, double right = 100.0){
    for(int i = 0; i < 200; i++){
        double mid1 = (2 * left + right) / 3;
        double mid2 = (left + 2 * right) / 3;
        if( searchY(mid1) > searchY(mid2) ){
            right = mid2;
        }else{
            left = mid1;
        }
    }
    return searchY(left);
}

int main(){
    while( cin >> n , n ){
        for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> l[i];
        double ans = sqrt(searchXY());
        printf("%.07f\n", ans);
    }
}