思路与算法我们先使用 Andrew 算法求出所有点对应的凸包 convexHull。如果三角形的某一点不在凸包上我们以其余两点的边为底那么我们总可以在凸包上找到一个点使得该点到此边的高大于原来的点到此边的高因此面积最大的三角形的三个点都在凸包上。在凸包 convexHull 上枚举三角形先枚举点 i然后枚举点 j最后枚举点 k其中 ijk。在固定点 i 和 j 后三角形的面积与 k 的关系是一个凸曲线因此三角形只在 k 为极点时面积最大。在固定点 i 时该极点在随点 j 增大而增大因此在搜索极点只需要从上次的极点位置开始搜索。所以我们不需要枚举点 k只需要搜索点 i 和 j 对应的极点然后求解三角形面积。返回最大的三角形面积。代码Python3class 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 ansJavaclass Solution { public double largestTriangleArea(int[][] points) { int[][] convexHull getConvexHull(points); int n convexHull.length; double ret 0.0; for (int i 0; i n; i) { for (int j i 1, k i 2; j 1 n; j) { while (k 1 n) { double curArea triangleArea(convexHull[i][0], convexHull[i][1], convexHull[j][0], convexHull[j][1], convexHull[k][0], convexHull[k][1]); double nextArea triangleArea(convexHull[i][0], convexHull[i][1], convexHull[j][0], convexHull[j][1], convexHull[k 1][0], convexHull[k 1][1]); if (curArea nextArea) { break; } k; } double area triangleArea(convexHull[i][0], convexHull[i][1], convexHull[j][0], convexHull[j][1], convexHull[k][0], convexHull[k][1]); ret Math.max(ret, area); } } return ret; } public int[][] getConvexHull(int[][] points) { int n points.length; if (n 4) { return points; } /* 按照 x 大小进行排序如果 x 相同则按照 y 的大小进行排序 */ Arrays.sort(points, (a, b) - { if (a[0] b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); Listint[] hull new ArrayListint[](); /* 求出凸包的下半部分 */ for (int i 0; i n; i) { while (hull.size() 1 cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) 0) { hull.remove(hull.size() - 1); } hull.add(points[i]); } int m hull.size(); /* 求出凸包的上半部分 */ for (int i n - 2; i 0; i--) { while (hull.size() m cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) 0) { hull.remove(hull.size() - 1); } hull.add(points[i]); } /* hull[0] 同时参与凸包的上半部分检测因此需去掉重复的 hull[0] */ hull.remove(hull.size() - 1); m hull.size(); int[][] hullArr new int[m][]; for (int i 0; i m; i) { hullArr[i] hull.get(i); } return hullArr; } public double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) { return 0.5 * Math.abs(x1 * y2 x2 * y3 x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2); } public int cross(int[] p, int[] q, int[] r) { return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]); } }
