(o_o)

ブログ。

AOJ1177 番犬派遣会社

高難度の場合分けゲーとして名高いこの問題だが、最近割と良さげな解法を思いついたので実装してみた。

STEP 1
原点から引数で与えられる点Pまでの建物の内部を通らない最短の道のりを求めるような関数を作る
原点とその点を結ぶ線分が建物の内部を通らないときは、その線分の長さが最短である。
そうでないときは、以下のようなグラフを作って、最短経路を求めてやればいい。f:id:asi1024:20141202075907p:plain
原点と点Pと長方形の頂点をグラフの頂点として、長方形の内部を通らない線分をグラフの頂点として追加すればよい。
ただし,点Pが長方形の内部にある場合は,INFを返すこと.

STEP 2
まず、原点を中心に半径lenの円を描く。
次に、長方形の各頂点について、その頂点までの原点からの最短の道のりを求め、その長さをlenから引いた長さを半径とした円をその頂点を中心に描く。ただし、その頂点までの最短の道のりの長さがlen以上である場合(つまりその頂点に番犬が到達できない場合)は円を描かない。
そして、円と建物の交点、円と円の交点を列挙する。
f:id:asi1024:20141202075909p:plain

STEP 3
それぞれの円について、STEP 2で列挙した交点のうちその円周上に乗っているもののみを取り出し、円の中心からの角度の順にソートする。これで、フェンスの候補となる円弧を列挙することができる。後は、円弧からランダムに1点選び原点までの最短の道のりを求め、これがlenの値と一致すれば非常に高い確率でこの円弧はフェンスである。
f:id:asi1024:20141202075910p:plain


この方法だと建物が複数個ある場合でも簡単に実装できそう。