AOJ 1342 Don't Burst the Balloon

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1342

解法

3次元幾何に見せかけた2次元幾何．
球の半径Rを決めた時，上から見て中心をどこにおけるかをイメージする．
すると針と球の条件は，ある円があってその外側に中心を置く，という感じになる．この円の半径は針の高さとRから簡単に求まる．
同様に壁との関係はある正方形があってその内部，になる．

こうして得られた正方形と円（針ごとに1つある）にたいして，適当に点を選んでその点が条件を満たすか考える．この点は，円と円の交点，円と正方形の交点，正方形の4隅を選べば十分．条件を満たすか確認するときは若干制約を緩くしておく（そうしないと周上にいる判定になってしまう）．

これができたら，あとは R で二分探索しておわり．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using point = complex<ld>;

// 略

int main() {
    int n, w;
    while(cin >> n >> w, n) {
        vector<ld> x(n), y(n), h(n);
        for(int i = 0; i < n; ++i) {
            cin >> x[i] >> y[i] >> h[i];
        }

        auto check = [&](const ld R) {
            vector<circle> cs(n);
            for(int i = 0; i < n; ++i) {
                if(h[i] <= R) cs[i].r = sqrt(2 * R * h[i] - h[i] * h[i]);
                else          cs[i].r = R;
                cs[i].p = point(x[i], y[i]);
            }

            const ld margin = (w <= R ? sqrt(2 * R * w - w * w) : R);
            if(margin >= 50) return false;

            vector<segment> ss;
            ss.emplace_back(point(margin, margin), point(100 - margin, margin));
            ss.emplace_back(point(margin, margin), point(margin, 100 - margin));
            ss.emplace_back(point(100 - margin, margin), point(100 - margin, 100 - margin));
            ss.emplace_back(point(margin, 100 - margin), point(100 - margin, 100 - margin));

            vector<point> ps = {point(margin, margin), point(margin, 100 - margin),
                                point(100 - margin, margin), point(100 - margin, 100 - margin)};
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < 4; ++j) {
                    for(auto&& p : is_sc(cs[i], ss[j])) ps.push_back(p);
                }
                for(int j = i + 1; j < n; ++j) {
                    for(auto&& p : is_cc(cs[i], cs[j])) ps.push_back(p);
                }
            }

            bool ok = false;
            for(auto& p : ps) {
                bool b = true;
                for(auto& c : cs) {
                    b &= abs(p - c.p) >= c.r - eps;
                }
                b &= real(p) >= margin - eps && real(p) - eps <= 100 - margin;
                b &= imag(p) >= margin - eps && imag(p) - eps <= 100 - margin;

                ok |= b;
            }

            return ok;
        };

        ld lb = 0, ub = 1e9;
        for(int lp = 0; lp < 50; ++lp) {
            const ld mid = (ub + lb) / 2;
            if(check(mid)) lb = mid;
            else           ub = mid;
        }

        cout << fixed << setprecision(10) << lb << endl;
    }
}

感想

なんか前書いた時バグった記憶があるんだけど，今書いたら15分ぐらいでかけてよかった．