Farmland (UVa Live Archive Asia - Site 4 (Korea) - 2001/2002 Taejon (Korea))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2327

問題

連結で単純な平面グラフを与えるので、長さkの閉路で内部に頂点、辺を含まない物は何個存在するか。
3<=頂点の個数<200
x,y<=1000(整数)

解法

まず、各頂点の辺を角度順にソートする。次に開始地点の枝を決め、頂点で反時計回りに回りながら最初の枝に戻って来るまで探索をする。探索中に同じ頂点を2回通るとそれは内部に辺を含む閉路になる。あとはそれが長さkの閉路かどうかをチェックすれば良い。
外周は含めていはいけないので、十分遠い場所に番兵の頂点を追加し、一番端の頂点と辺で繋げた。