Pythonで最大の三角形の領域

平面上の点のリストがあるとします。 3つの点で形成できる最大の三角形の領域を見つける必要があります。

したがって、入力が[[0,0]、[0,1]、[1,0]、[0,2]、[2,0]]の場合、出力は2

これを解決するには、次の手順に従います-

• res：=0
• N：=ポイントリストのサイズ
• 0からN-2の範囲のiの場合、do
  • i +1からN-1の範囲のjの場合、do
    • i + 2からNの範囲のkについては、
      • （x1、y1）：=points [i]、
      • （x2、y2）：=points [j]、
      • （x3、y3）：=ポイント[k]
      • res：=resの最大値、0.5 * | x1 *（y2-y3）+ x2 *（y3-y1）+ x3 *（y1-y2）
• return res

理解を深めるために、次の実装を見てみましょう-

例

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