ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

AOJ 1194 バンパイア

バンパイア | Aizu Online Judge

各整数x座標において、どの時間までなら建物があるかを調べればよい。
(このx座標が建物の境界の場合とかに注意。特に座標-r,rとかは危険)

あさがおと加瀬さん。 (ひらり、コミックス)

あさがおと加瀬さん。 (ひらり、コミックス)

void solve(double r,int n){
    vector<int> xl(n),xr(n),h(n);
    map<int,int> H;
    rep(i,n){
        cin >> xl[i] >> xr[i] >> h[i];
        for(int j=xl[i];j<xr[i];j++){
            H[j] = max(h[i],H[j]);
        }
    }

    double ans = 100;
    for(int x=-r;x<=r;x++){
        double y = min(H[x-1],H[x]);
        if(x == -r) y = H[x];
        if(x == r) y = H[x-1];
        double t = y + r - sqrt(r*r-x*x);
        ans = min(ans,t);
    }
    cout << Double(ans) << endl;
}


int main(){
    int r,n;
    int cnt = 0;
    while(1){
        cin >> r >> n;
        if(!r and !n) break;
        solve(r,n);
    }
}