2013国内予選 E. つながれた風船

ACM-ICPC

E. つながれた風船

解法

  • 色々やり方はあるけど、ここでは円の問題に落として2分探索する方針
  • 高さhまで風船が上げられるかという問題を考える
    • 高さを決めれば、各ヒモの先端がどの範囲を動けるかは円で表せる
    • その円に共通部分が存在すれば、風船は高さhに上がる事ができる
  • 共通部分があれば、それは2つの円の交点か、円の中心のどれかを含む
    • ある円が他の全ての円に内包されるケースがあるので、交点だけだと不十分
    • 含む点の全ての候補について、その点が全ての円に内包されてるか調べれば良い
      • 1個でも内包しない円があれば、その点は共通部分上には無い
  • 高さhに上がれない -> 高さh'(>h)にも上がれない なので、あとは2分探索
#include <iostream>
#include <vector>
#include <complex>
#include <cstdio>
#include <cmath>

using namespace std;

const double EPS = 1e-10;

typedef complex<double> P;
typedef pair<P,double> circle;

double cross(P a, P b) { return imag(conj(a)*b); }

bool containPoint(const circle& c, const P& p){
    double dist = abs(c.first-p);
    return dist < c.second+EPS;
}

bool crossCircle(const circle& c1, const circle& c2){
    double r1 = c1.second;
    double r2 = c2.second;
    double d = abs(c1.first-c2.first);
    if(d<r1||d<r2)
        return d-abs(r1-r2)>EPS;
    return r1+r2-d>-EPS;
}

void crossPoint(vector<P> &res, const circle& c1, const circle& c2){
    double r1 = c1.second;
    double r2 = c2.second;
    double r3 = abs(c1.first-c2.first);
    double rc = (r3*r3+r1*r1-r2*r2)/(2*r3);
    double rs = sqrt(r1*r1-rc*rc);
    P dif = (c2.first-c1.first)/r3;
    res.push_back(c1.first+dif*P(rc, rs));
    res.push_back(c1.first+dif*P(rc,-rs));
}

bool valid(const vector<circle>& vc){
    vector<P> vp;
    for(int i=0;i<vc.size();i++){
        vp.push_back(vc[i].first);
        for(int j=i+1;j<vc.size();j++){
            if(crossCircle(vc[i], vc[j]))
                crossPoint(vp, vc[i], vc[j]);
        }
    }
    for(int i=0;i<vp.size();i++){
        bool ok = true;
        for(int j=0;j<vc.size();j++)
            if(!containPoint(vc[j], vp[i])) ok = false;
        if(ok) return true;
    }
    return false;
}

int main(){
    int n;
    int x[10], y[10], l[10]; 
    while(cin >> n &&  n){
        int minL = 100000;
        for(int i=0;i<n;i++){
            cin >> x[i] >> y[i] >> l[i];
            minL = min(minL, l[i]);
        }
        double low = 1.0, high = minL;
        for(int i=0;i<200;i++){
            double mid = 0.5*(low+high);
            vector<circle> vc;
            for(int j=0;j<n;j++){
                double r = sqrt(l[j]*l[j]-mid*mid);
                vc.push_back(make_pair(P(x[j], y[j]), r));
            }
            if(valid(vc)) low  = mid;
            else          high = mid;
        }
        printf("%.8lf\n", 0.5*(low+high));
    }
}