一般的な位置にある平面内のN個の点のリスト（3つは同一線上にない）が与えられた場合、N個の元の点のペアと同一線上にない新しい点pを見つけます。
明らかに、平面内のすべての点を検索することはできません。与えられた点で形成できるすべての線の一致点を見つけることから始めました。または、それらと円を描くことから始めました。すべてを確認する方法がわかりません。ポイント。
http://introcs.cs.princeton.edu/java/42sort/にある質問
有名なアルゴリズムの本でこの質問を見つけましたが、それは答えられることを意味しますが、最適な解決策を考えることができないので、誰かがそれを知っている場合は答えられるように、ここに投稿します
実際には、単純な O(nlogn) アルゴリズムを使用して解決できます。これを O(n) に改善します。一番下のポイントに A という名前を付けます (同点の場合は、x 座標が小さい方を選択します)。CCW を使用して、残りのポイントを時計回りに並べ替えることができます。ソートされた順序で各ポイントを処理すると、ポイント A と下の軸 (これらを U、V とする) に対して異なる角度を持つ任意の 2 つの連続するポイントの間には、U <= c で、角度 c を持つポイントがないことがわかります。 <= V. したがって、このセクションに任意のポイントを追加でき、セットの他のポイントと同一線上にないことが保証されます。したがって、隣接する点のペアを 1 つ見つけるだけで済みます。したがって、O(n) 時間で A の最小角度と 2 番目の最小角度 (これらは異なるはずです) を見つけ、それらの間の任意の点を選択します。