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

AOJ 2609 : Wave Attack

幾何

Wave Attack | Aizu Online Judge

問題概要

  • W*Hのフィールド内に衝撃波発生装置と魔王がいます。
  • どちらもフィールドの隅にはありません。
  • 衝撃波が速度vでt秒間広がりつづけるので魔王にあたった回数を求めて下さい。
  • 衝撃波は壁に鏡の反射をします。

解法

  • 反射は鏡像
  • 僕の解法は公式解の一億倍頭の悪い解法なので参考にしないことをおすすめします。
  • フィールドを半径vt分だけ拡張して円の中にある魔王の数を数える。
  • そのままやると勿論TLEなので円周上にあるフィールドのみに対し円の中にいるかどうか判定してそれ以外は円の内部と判定する。(↓こんな感じ)

    f:id:satelliteyezu:20160420182953p:plain

  • バグを生む
ソースコード

感想

良い解法は↓

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2013%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95&openfile=Day3-C.pdf

良い解法と良い実装法を思いつかないと幾何はきびしい