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

土下座しながら探索中

主に競技プログラミング

AOJ 2073 : The Phantom

問題リンク : The Phantom | Aizu Online Judge

問題概要 :
2次元平面上に2枚の鏡と幽霊がいる
鏡と幽霊はそれぞれ線分と点として表される
鏡に映る幽霊の数を出力せよ
ただし、その数が100を超える場合は"TOO MANY"と出力せよ

解法 :

よくあるビームと鏡の反射の問題( Laser Beam Reflections, Putter, Strange Opera house, Strange Opera House II,など )と同様に考える
まだ Laser Beam Reflections も Putter も解いたことがないなら先にそちらを解いてくると良い
( Strange Opera House はこの問題よりも難しい(断言)ので優先してやらなくても良い )
幽霊のいる位置からビームを打ち、それぞれの鏡に何回か反射させて再度幽霊にビームを当てることができるような鏡の反射の順番の数が答えとなる

鏡の反転を間違えたりコーナーケースにやられたりして辛かったので
JAGのページに上がってた解答コードを読んで解いた
以下はその解説

まず、TOO MANY となるようなケースについて考えてみるが、これは様々なケースがある
これらのケースを最初に取り除いておきたかったが出来そうにないので適当な回数処理を行ってもまだ処理が続くようなら無限ループとみなし処理を終えるものとする

幽霊の位置からビームを任意の方向に飛ばし鏡に反射させ、再度幽霊に当てることが出来るかどうかを
鏡に1回反射させた場合、2回反射させた場合、3回、、と順番に計算する
1回であれば、各鏡を基準に幽霊の位置を対称に移し、元の幽霊の位置から対称の点に鏡を通して直接当てることができるかどうかで判定できる(といってもここにもコーナーケースがあって一筋縄ではいかないが)
2回目に入る前に、各鏡の位置、幽霊の像の位置、幽霊が最初の鏡を通して見える角度を更新する
あとはこれを適当な回数繰り返す
頑張ると溶ける

以下 Sample Input の最初のケースの最初の方の図
厳密なものではない



以下コーナーになりそうなケースの例
これも厳密ではない 
このような感じの入力で、鏡を対称移動させたら以前よりも近くにくる場合はコーナーになるかも

コード :

AOJ で見れますので