AOJ 1194 バンパイア
各整数x座標において、どの時間までなら建物があるかを調べればよい。
(このx座標が建物の境界の場合とかに注意。特に座標-r,rとかは危険)
- 作者: 高嶋ひろみ
- 出版社/メーカー: 新書館
- 発売日: 2012/07/28
- メディア: コミック
- 購入: 2人 クリック: 5回
- この商品を含むブログ (10件) を見る
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); } }