Python 中的三角形最大面積

假設我們在一個平面上有一個點列表。我們必須找出由這列表中的任意 3 個點能構成的最大三角形面積。

所以，如果輸入是像 [[0,0],[0,1],[1,0],[0,2],[2,0]]，那麼輸出將是 2

為了解決此問題，我們將按照以下步驟操作 −

• res := 0
• N := 點列表的大小
• 對於 i 從 0 到 N - 2，操作
  • 對於 j 從 i + 1 到 N - 1，操作
    • 對於 k 從 i + 2 到 N，操作
      • (x1, y1) := points[i],
      • (x2, y2) := points[j],
      • (x3, y3) := points[k]
      • res := res 的最大值，0.5 * |x1 *(y2 - y3) + x2 *(y3 - y1) + x3 *(y1 - y2)|
• 返回 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

Arnab Chakraborty

更新於: 2020 年 7 月 4 日

585 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始