AOJ 1189 つながれた風船

目からウロコおじさんだった。

問題

つながれた風船 | Aizu Online Judge

解法

風船のx, yの座標(X, Y)を一つに決めると,z^2の値としてありえるのは

min()(i = 0〜n-1)

となります(はそれぞれ杭に繋がれた糸の長さ,杭のxy座標)。これはに関して上に凸な関数です。

よって,X, Yについて3分探索すれば答えを求めることが出来ます。

一応注意しておくと,上の式の時点でsqrtを使ってしまうと正しい答えを求めることが出来ません。z^2が0未満になるところではすべてsqrtが0を返してしまうので上に凸な関数にならないからです。

double x[11], y[11], l[11];

double square(double X) {return X*X;}

double calc(int n, double X, double Y) {
    double ret = 1e9;
    for (int i = 0; i < n; i++) {
        ret = min(ret, /*sqrt*/(square(l[i]) - square(x[i]-X) - square(y[i]-Y)));
    }
    return ret;
}

double searchY(int n, double x) {
    double left = -100, right = 100;
    for (int t = 0; t < 200; t++) {
        double m1 = (2*left+right) / 3;
        double m2 = (left+2*right) / 3;
        double M1 = calc(n, x, m1);
        double M2 = calc(n, x, m2);
        if (M1 > M2) {
            right = m2;
        } else {
            left = m1;
        }
    }
    return calc(n, x, (right+left)/2);
}

double search(int n) {
    double left = -100, right = 100;
    for (int t = 0; t < 200; t++) {
        double m1 = (2*left+right) / 3;
        double m2 = (left+2*right) / 3;
        double M1 = searchY(n, m1);
        double M2 = searchY(n, m2);
        if (M1 > M2) {
            right = m2;
        } else {
            left = m1;
        }
    }
    return searchY(n, (left+right)/2);
}

void solve(int n) {
    printf("%.15lf\n", sqrt(search(n)));
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i] >> l[i];
        }
        solve(n);
    }
    return 0;
}