Description:
多角形内の任意の点と、ある点Cを結ぶ線分が多角形に包含されている時、その多角形をstar shapeと呼び、点Cを多角形のcenterと呼ぶ。
n 角形(4 <=n <=50)が与えられるので、それが star shapeかどうかを判定して欲しい。
x,y座標の取りうる値は0以上1万以下の整数とする。
また、多角形の辺を延長し、直線とした時に、どの3つの辺も1点では交わらない。
Answer:
辺を延長した直線で領域を分割すると、片方の領域からはこの辺を見る事が出来るが、反対側は見ることが出来ない。
もし多角形がstar shapeなら、centerに成り得る点とそうで無い点の境界があり、2辺を延長した直線の交点のうちの少なくとも1つがその位置に来るはずである。
よって、このような点を全てチェックし、centerとなっているかどうかを調べればよい。
この点と多角形の頂点とを結ぶ線分が全て多角形に含まれているかで、centerかどうかは判断できる。
計算時間は、center候補(n^2) * 各頂点と結ぶ線分(n) * 包含判定(n) の、O(n^4)となる。
Source: