AOJ 1194 : Vampire
トラウマ問題
問題概要
- N個の長方形が与えられます。
各長方形の下底は必ずX軸に接している。 - 半径Rの円が(0,-R)が秒速1で上に上がっていきます。
- 円が長方形に覆われなくなった瞬間の時間を答えて下さい。
- 長方形同士で重なったりもあるので注意。
解法
- イベント点を列挙して各点についてその点をギリギリ通る円を考えそれが長方形の内部かどうかを判定する。
- イベント点 is 何？
-
ギリギリ通る円 is 何？
イベント点とy座標との距離をxとすれば三平方とか使って"ここ"が簡単に求まります。 - あとは、その円に対し全てのイベント点が含まれていなければOK。
- 国内予選でぼくは二分探索しようとして失敗、その後この解法聞いて簡単じゃん！と思いました。
- イベント点どうやって列挙するんだろう…
- いろいろ悩んだ結果、多分こんな感じのが一番実装楽そうかなと思いました↓
-
まずこんな感じに長方形の部分を塗りつぶします。
-
で現在見ている点をこのピンクとします。
こいつを↓,→,↑の順で行けるかどうか判定して動かしていきます。
-
- でピンクの点が通った点がイベント点になる。
- 列挙できたらあとは勝ち。
- かと思いきや円が長方形の内部にあるの判定に反例があって
- こういうときにイベント点が内包されてるかどうかだけじゃだめ。
- y軸にあるイベント点が１つでも円の中心のy座標よりも小さかったら円じゃないという判定をすれば通りました。
ソースコード
感想
１年ぶりだし解法知ってるしさすがに解けるだろうと思ったら普通に難しかった。
スーパー苦手。でも、綺麗にかけるとすっきりする。もっと楽な実装あるのかなぁとは思うけど。
幾何は解法にプラスどう実装したら楽かも考えなきゃいけない（修行あるのみ）
