AOJ 1342 Don't Burst the Balloon
解法
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分ぐらいでかけてよかった.