AOJ 0237 （The Last Door : 最後の扉）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0237
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0237
【解説】
幾何+グラフ問題。
まずは、ある三角形が光ったときに、その光が触れる三角形（以下、"出力三角形"）を求める。三角形が放つ光の範囲については、
- 三角形ABCの各辺の長さを求め、どの頂点が頂角に当たるかを判定する。
- 底辺の中点から頂角へのベクトルを作成する。
- 2.のベクトルを正規化し、光の伸びる長さdを掛ける。
- 原点Oからそれぞれの底角のベクトルに3.のベクトルを加える。
の処理を行うことで求めることができる。（底角の2点と4.の処理で求めた2点が放つ光の範囲の長方形）
この長方形と自分自身以外の各三角形が交差するかを求めればよい。
交差判定については、
- 長方形の辺上を含む内部に三角形のいずれかの頂点が入っている。
- 三角形の辺上を含む内部に長方形のいずれかの頂点が入っている。
のうち、いずれかを満たしているかを判定すればよい。これについては、図形上の各辺を周回するよう辺を辿ったときに、候補となる点Pから辺の終点へのベクトルと辺ベクトルとの外積の正負が全ての辺において同一となるかどうかで調べることができる。
なお、1 点とひとつの直線の距離が 0.01 以下の場合には、この点はこの直線上にあるとして処理する条件のため、先に点Pと辺までの距離を調べて置き、0.01以下であれば重なっていると判定している。
上記の処理はO(N^2)で調べられ、三角形の数は高々100個のため、十分処理時間内で判定可能である。
あとは、各三角形について、その三角形を光らせる他の三角形（以下、"入力三角形"とする。）が無いものの個数を調べていけばよい。
三角形と入力三角形・出力三角形の関係性は、三角形をノードと捉えた有向グラフと考えることができる。よって、基本的には入力三角形が0となる三角形の数を数えていけばよいが、入力三角形との間で閉路を構成している場合は、入力三角形の数が0以外でも該当する三角形に触れなければならない場合がある。
例として、1⇒2、2⇒3、3⇒1、4⇒5、5⇒4のような関係であれば、全てにおいて入力三角形を持つが、最低2つの三角形（1or2or3、4or5）に触れる必要がある。
閉路を構成している三角形については、その閉路を構成している三角形群を1つの三角形として捉えることができる。例えば、1,2,3の三角形で閉路を構成していれば、1,2,3を1つの三角形として捉え、1,2,3への入力三角形をその三角形の入力三角形、1,2,3からの出力三角形をその三角形の出力三角形として扱っても差し支えない。
よって強連結成分分解を行い、それぞれの連結成分に対して、同一成分外の入力三角形の個数を数えていくことで、触れる必要のある回数を求めることができる。
【コード】
