Pythonで点のリストから作れる最大の三角形の面積を求める方法

平面上に与えられた点のリストの中から、任意の3点を選んで作ることができる三角形のうち、最も大きな面積を持つものを求める問題です。

例えば、入力が [[0,0],[0,1],[1,0],[0,2],[2,0]] の場合、出力は 2 となります。

解法のアプローチ

この問題は、すべての3点の組み合わせについて三角形の面積を計算し、その最大値を求めることで解けます。手順は以下の通りです。

• 結果を格納する変数 res を 0 で初期化する
• 点のリストのサイズを N とする
• 三重ループで、i、j、k の3つのインデックスの組み合わせをすべて列挙する（i < j < k）
• 各組み合わせに対して、3点の座標 (x1, y1)、(x2, y2)、(x3, y3) を取得する
• 座標を使った面積公式「0.5 × |x1(y2 − y3) + x2(y3 − y1) + x3(y1 − y2)|」で三角形の面積を計算し、res より大きければ更新する

ここで使っている公式は、3点の座標から三角形の面積を求める「靴紐の公式（Shoelace formula）」の応用です。絶対値を取ることで、点の並び順に関係なく正の面積が得られます。

実装例

class Solution:
    def largestTriangleArea(self, points):
        res = 0
        N = len(points)
        for i in range(N - 2):
            for j in range(i + 1, N - 1):
                for k in range(i + 2, N):
                    (x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k]
                    res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
        return res

ob = Solution()
print(ob.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))

入力

[[0,0],[0,1],[1,0],[0,2],[2,0]]

出力

2.0

計算量について

この解法は3重ループを使用するため、時間計算量は O(N³) となります。点の数 N が小さい場合には十分実用的ですが、N が大きくなると処理時間が急増します。凸包（Convex Hull）を先に計算して候補となる点を絞り込むことで、実際の計算量を削減できる場合があります。なお、最大の三角形の頂点は必ず凸包上に存在することが知られているため、この最適化は有効です。