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

更新于: 2020 年 7 月 4 日

585 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告