题目内容
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
示例：
输入: 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