「LeetCode算法精讲」从集合取3个点，组成最大三角形(Python)

题目内容

给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。

示例：

 输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
 输出: 2
 解释: 
 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。

注意：

• 3 <= points.length <= 50.
• 不存在重复的点。
• -50 <= pointsi <= 50.
• 结果误差值在 10^-6 以内都认为是正确答案。

来源：力扣（LeetCode）

链接：
https://leetcode-cn.com/problems/largest-triangle-area

解法效率

LeetCode的Python执行用时随缘，只要时间复杂度没有明显差异，执行用时一般都在同一个量级，仅作参考意义。

解法一（海伦公式求面积）

根据题意，我们最先想到的就是遍历所有可能的三个点的组合，找出能够组成的最大三角形面积。

在具体的实现中，我们使用海伦公式求三角形面积。实现如下：

 def largestTriangleArea(self, points: List[List[int]]) -> float:
     def distance(pp1, pp2):
         return pow(pow(pp1[0] - pp2[0], 2) + pow(pp1[1] - pp2[1], 2), 0.5)
 
     ans = 0
     for i1 in range(len(points)):
         p1 = points[i1]
         for i2 in range(i1 + 1, len(points)):
             p2 = points[i2]
             for i3 in range(i2 + 1, len(points)):
                 p3 = points[i3]
                 a = distance(p1, p2)
                 b = distance(p1, p3)
                 c = distance(p2, p3)
                 p = (a + b + c) / 2
                 t = p * (p - a) * (p - b) * (p - c)
                 if t > 0:
                     s = pow(p * (p - a) * (p - b) * (p - c), 0.5)  # 海伦公式求面积
                     ans = max(ans, s)
     return round(ans, 2)

解法二（顶点坐标求面积）

【思路】

我们发现海伦公式在求解三角形面积时，需要先计算三边长，再由三边长计算三角形面积，在计算过程中，需要3次开方运算，效率较低。

因为我们已知三角形的顶点坐标，所以我们可以直接使用如下公式。

已知三角形的三个顶点坐标A(x1,y1)、B(x2,y2)、C(x3,y3)，则三角形面积为：

S=abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))/2

实现如下：

 def largestTriangleArea(self, points: List[List[int]]) -> float:
     ans = 0
     for i1 in range(len(points)):
         [x1, y1] = points[i1]
         for i2 in range(i1 + 1, len(points)):
             [x2, y2] = points[i2]
             for i3 in range(i2 + 1, len(points)):
                 [x3, y3] = points[i3]
                 s = abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))) / 2
                 ans = max(ans, s)
     return ans

解法三（使用组合）

我们使用itertools中的组合函数，让我们的代码更优雅。

 def largestTriangleArea(self, points: List[List[int]]) -> float:
     return max(abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
                for (x1, y1), (x2, y2), (x3, y3) in itertools.combinations(points, 3)) / 2