判定点が不規則ポリゴン内部にあるかどうかの問題

問題は次のとおりです.

                     ，             ，  ：                       ？

  ：
       ？             ，           。      ，             。

もちろん、グーグルと度娘に詳しい学生は、正しいかどうか、国内の海外の解法を探しています.もちろんACMの試合に参加したことがある学生も勉強したり、訓練したり、試合をしたりして、この問題にぶつかったかもしれません.
私は自分が考えずに直接検索したことを残念に思っています.あなたが自己向上の機会を失ったからです.
ある回答者が述べたように、「蚊取り線香を作ったあなたは計算してみますか?」題名自体が勝手なので、蚊取り線香の形にするのも問題に合います.
この問題はもともと出会う時、いくつかの案を考えて、いくつかは答えと同じで、あるものは違います.今1つのあまり同じではありません出てきてみんなと分かち合って、个人の感じの効率はとても高いべきで、みんなはレンガをたたいて軽くて、ほほほ.
私は任意の形の多角形を、釘で留めた輪ゴムよりも、どのように形を変えたいのか、もっと輪ゴムを増やせばいいのです.しかし、一つずつ釘を抜いて、釘の数が3つになると、それが三角形になり、その結果、三角形の内部に点があるかどうかの問題に変わります.
もちろん、釘を抜くときは、この点がちょうど釘と縁の2つの釘を抜く三角形の中にある場合は、結果が正しいため、まずこの釘を抜かないことに注意しましょう.
また、釘を抜くときに、隣接する3つの点が一直線になると、真ん中の1つの点を取り除くことで、三角形ではなく3点一線が最終的に形成されることを避けることができます.
OK、アルゴリズムの考え方が出てきても、再帰をして、毎回1周して、取り除くことができる釘を取り除いて、まだ3つの釘があるまで.
n個の釘を設け,最後にn−3個の釘を常に取り除くことで,結果を判定できる.従って時間複雑度はO(n)である.