AOJ 0115 Starship UAZ Advance

アドベントカレンダー(後編)を書くのがつらい.
@に「AOJ 0115ときましょう!!!レイトレーシングするだけ!!!」と言われたのが運の尽きであった……(うちの学校では4年次にCGという講義でレイトレーシングもろもろについて学ぶので,彼はちょうどその辺りについて教わったらしい)
問題URL : Starship UAZ Advance | Aizu Online Judge
解法としては,まず三角形の法線ベクトルを外積とって求めて,その法線ベクトルを用いてUAZ号から敵に向かって伸びる半直線と三角形を含む平面との交点を求める.
その得た交点が三角形内部にあるかどうかを,T1, T2, T3のそれぞれの面積の合計が三角形の合計と等しかったら内部にある = バリアに弾かれるのでMISS,そうでなかったらHITという感じ.
f:id:li_saku:20141224072807p:plain
教訓としては,EPSちゃんと使うというのと,めんどくさがって超破壊的変更をしまくる構造体を使うなということでした(ちゃんとoperatorを定義しようという話)
あと半直線かどうかというのに気をつけようという感じ(UAZ号...敵...バリアみたいなのだと,当たる判定はされるんだけど実際にはバリアに当たる前に敵に当たるので,バリアのどっち側に2頂点があるのかを調べるべき:これは内積の符号でわかるので嬉しい)
これをライブラリに使うのはさすがに苦行なのでちゃんと書きます…