AOJ 2609 : Wave Attack
Wave Attack | Aizu Online Judge
問題概要
- W*Hのフィールド内に衝撃波発生装置と魔王がいます。
- どちらもフィールドの隅にはありません。
- 衝撃波が速度vでt秒間広がりつづけるので魔王にあたった回数を求めて下さい。
- 衝撃波は壁に鏡の反射をします。
解法
- 反射は鏡像
- 僕の解法は公式解の一億倍頭の悪い解法なので参考にしないことをおすすめします。
- フィールドを半径vt分だけ拡張して円の中にある魔王の数を数える。
- そのままやると勿論TLEなので円周上にあるフィールドのみに対し円の中にいるかどうか判定してそれ以外は円の内部と判定する。(↓こんな感じ)
- バグを生む
ソースコード
感想
良い解法は↓
良い解法と良い実装法を思いつかないと幾何はきびしい