読者です 読者をやめる 読者になる 読者になる

kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

AOJ-1194 : バンパイア

プログラミングコンテスト 幾何問題

Vampire | Aizu Online Judge

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


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

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

// 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;
}