質問はすでに回答されていますが、私が直面している主な問題は、回答の1つを理解することです..
https://stackoverflow.com/a/1621913/2673063から
次のアルゴリズムはどうO(n)ですか?
最初にポイントを並べ替える/凸包を計算する (O(n log n) 時間) 必要に応じて、多角形に表示される順序で周期的に並べ替えられたポイントを持つ凸多角形/凸包があると仮定できます。ポイントを 1、2、3、…、n と呼びます。(可変) ポイント A、B、および C を、それぞれ 1、2、および 3 として開始します (周期的な順序で)。ABC が最大面積の三角形になるまで、A、B、C を移動します。(この考え方は、直径 (最も遠いペア) を計算するときに使用される回転キャリパー法に似ています。)
A と B を固定して、三角形の面積が増加する限り、つまり、面積(A、B、C) ≤ 面積(A、B、C+1)。この点 C は、固定された A と B の Area(ABC) を最大化する点になります (つまり、関数 Area(ABC) は C の関数として単峰性です)。
次に、B を (A と C を変更せずに) 進めると、領域が増加します。その場合は、上記のように C を進めます。次に、可能であれば B をもう一度進めます。これにより、A を頂点の 1 つとする最大面積の三角形が得られます。(ここまでの部分は簡単に証明できるはずで、これを各 A ごとに単純に行うと O(n2) になります。しかし、読み進めてください。) では、A をもう一度進めて、面積などを改善する場合など。ネストされた" ループでは、B と C は常に "前方" に進み、合計で最大 2n 回進む (同様に A は最大 n 回進む) ため、全体が O(n) 時間で実行されることに注意してください。
