AOJ-1194 : バンパイア

Vampire | Aizu Online Judge

バンパイアが日の光に当たらずに，無事に棺桶に戻りたい．幸運な事にたくさんのビルがあるため，ビルの影を利用して日に当たらず帰る事が出来そう．簡単のため，ビルのシルエットは長方形， 太陽は半径 r の円とする．太陽は秒速(0, 1)で，等速直線運動している．その状態で，太陽の光が遮られている最後の時間を出力する．

与えられるビルの範囲は負の値があるため，mapを使って，負の値でアクセス出来るようにしています．

太陽がビルからはみ出ているかは，太陽(円)の領域に，ビルの上部の点２つが含まれているかで判定しています．ビルの上部の点のどちらかが，含まれていれば太陽はビルからはみ出ています．円と点の距離の公式を使っています．

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

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
#include<iomanip>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int r, n;
map<int,map<int,double>> height;

bool judge(double base) {
	REP(x, -r, r) {
		double y = height[x][x+1] - base;
		if(x*x + y*y < r*r) {
			return true;
		}
		if((x+1)*(x+1) + y*y < r*r) {
			return true;
		}
	}
	return false;
}

int main() {
	cout << setprecision(5) << fixed;
	
	while(cin >> r >> n, r != 0) {	
		height.clear();
		double lx, rx, h;
		rep(i, n) {
			cin >> lx >> rx >> h;
			REP(x, lx, rx) {
				height[x][x+1] = max(h, height[x][x+1]);
			}
		}
		
		bool is_dead=false;
		double base = -r;
		double t = 0.0, step=0.0001;
		while(true) {
			base += step; 
			bool is_dead = judge(base);
			if(is_dead) break;
			t += step;
		}

		cout << t << endl;
	}
	return 0;
}