难度: Easy
给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。
示例 1：
输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出：2.00000 解释：输入中的 5 个点如上图所示，红色的三角形面积最大。
示例 2：
输入：points = [[1,0],[0,0],[0,1]] 输出：0.50000
提示：
3 <= points.length <= 50-50 <= xi, yi <= 50运行时间: 42 ms
内存: 16.1 MB
class Solution:
def getConvexHull(self, points: List[List[int]]) -> List[List[int]]:
def cross(p: List[int], q: List[int], r: List[int]) -> int:
return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])
n = len(points)
if n < 4:
return points
# 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
points.sort()
hull = []
# 求凸包的下半部分
for i, p in enumerate(points):
while len(hull) > 1 and cross(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
# 求凸包的上半部分
m = len(hull)
for i in range(n - 2, -1, -1):
while len(hull) > m and cross(hull[-2], hull[-1], points[i]) <= 0:
hull.pop()
hull.append(points[i])
hull.pop() # hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0]
return hull
def largestTriangleArea(self, points: List[List[int]]) -> float:
def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:
return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2
convexHull = self.getConvexHull(points)
ans, n = 0, len(convexHull)
for i, p in enumerate(convexHull):
k = i + 2
for j in range(i + 1, n - 1):
q = convexHull[j]
while k + 1 < n:
curArea = triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1])
nextArea = triangleArea(p[0], p[1], q[0], q[1], convexHull[k + 1][0], convexHull[k + 1][1])
if curArea >= nextArea:
break
k += 1
ans = max(ans, triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1]))
return ans
该题解采用的是计算凸包和在凸包上查找最大三角形面积的方法。首先，使用Graham扫描算法计算点集的凸包，这保证了三角形的顶点位于凸包的顶点上，这是因为非凸包点无法形成最大面积的三角形。计算凸包后，对凸包上的每对点（作为三角形的两个顶点），使用旋转卡壳技术优化地寻找第三个点，这个点使得三角形的面积最大。通过对每个固定的边，逐步旋转至最佳的第三点位置，可有效地找到最大面积。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def getConvexHull(self, points: List[List[int]]) -> List[List[int]]:
def cross(p: List[int], q: List[int], r: List[int]) -> int:
# 使用向量叉积判断点的相对位置
return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])
n = len(points)
if n < 4:
return points
# 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
points.sort()
hull = []
# 求凸包的下半部分
for i, p in enumerate(points):
while len(hull) > 1 and cross(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
# 求凸包的上半部分
m = len(hull)
for i in range(n - 2, -1, -1):
while len(hull) > m and cross(hull[-2], hull[-1], points[i]) <= 0:
hull.pop()
hull.append(points[i])
hull.pop() # 移除重复的起点
return hull
def largestTriangleArea(self, points: List[List[int]]) -> float:
def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:
# 计算三角形的面积
return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2
convexHull = self.getConvexHull(points)
ans, n = 0, len(convexHull)
for i, p in enumerate(convexHull):
k = i + 2
for j in range(i + 1, n - 1):
q = convexHull[j]
while k + 1 < n:
curArea = triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1])
nextArea = triangleArea(p[0], p[1], q[0], q[1], convexHull[k + 1][0], convexHull[k + 1][1])
if curArea >= nextArea:
break
k += 1
ans = max(ans, triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1]))
return ans
Graham扫描算法使用向量叉积来确定三个点的相对位置，进而决定是否将点包括在凸包内。向量叉积结果为正，表示三个点构成的转向是逆时针；为负则为顺时针；为零则三点共线。在构建凸包时，我们希望保留构成凸包边界的逆时针转向，因此，当叉积为非正时（即顺时针或共线），当前点不应加入凸包。这种方法确保了在处理边界点时，只有当新点能与已有的凸包边界维持逆时针关系时才被添加，从而正确地构造出凸包的下半部和上半部。
旋转卡壳技术优化了在凸包上寻找最大三角形面积的过程。传统方法需要对凸包上的每个点对进行三重循环查找最大面积，时间复杂度为O(n^3)。旋转卡壳技术通过固定两点，然后通过旋转找到使三角形面积最大的第三点，这一点通常是对腰的对角线方向上的点。核心原理是在固定一条边的情况下，第三点位置的最优解是单调的，即随着边的旋转，第三点也按一定方向移动，不需要每次都重头搜索，从而将搜索时间从线性减少到常数时间，整体算法复杂度降为O(n^2)。
在旋转卡壳技术中，对于凸包上的每对固定点（A和B），算法通过逐步旋转来选择作为第三点的C。由于凸包上的点是按顺序排列的，当从点A和点B出发，逐步增加第三点C的索引时，三角形ABC的面积会首先增加直到达到最大值，然后开始减小。这是因为凸包的性质保证了点的线性序，避免了内部的“突出”点干扰。一旦面积开始减少，就不再需要继续搜索，因为后续的三角形面积将会继续减小。这种方法确保了找到的第三点是能够使三角形面积最大化的点。