登录两种方法：枚举 / 凸包+旋转卡壳（Python/Java/C++/Go）
三角形面积公式
对于平面上的三个点 $P_1,P_2,P_3$，定义 $\mathbf{a} = \overrightarrow{P_1P_2}$，$\mathbf{b} = \overrightarrow{P_1P_3}$。
根据向量叉积的定义，$|| \mathbf{a} \times \mathbf{b} ||$ 是由 $\mathbf{a}$ 和 $\mathbf{b}$ 张成的平行四边形的面积。除以 $2$ 就得到了 $\triangle P_1P_2P_3$ 的面积。
严格来说，叉积是三维概念。这里把向量 $\mathbf{a}$ 和 $\mathbf{b}$ 视作 $z$ 方向为 $0$ 的三维向量。
设 $\mathbf{a} = (x_1,y_1)$，$\mathbf{b} = (x_2,y_2)$，根据叉积的计算公式，三角形面积为
$$
\dfrac{1}{2}|x_1y_2 - y_1x_2|
$$
上式中的 $(x_1,y_1)$ 来自 $P_1,P_2$ 的横坐标之差，纵坐标之差。$(x_2,y_2)$ 来自 $P_1,P_3$ 的横坐标之差，纵坐标之差。
方法一：暴力枚举
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
ans = 0
for p1, p2, p3 in combinations(points, 3):
x1, y1 = p2[0] - p1[0], p2[1] - p1[1]
x2, y2 = p3[0] - p1[0], p3[1] - p1[1]
ans = max(ans, abs(x1 * y2 - y1 * x2)) # 注意这里没有除以 2
return ans / 2
class Solution {
public double largestTriangleArea(int[][] points) {
int n = points.length;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int[] p1 = points[i], p2 = points[j], p3 = points[k];
int x1 = p2[0] - p1[0], y1 = p2[1] - p1[1];
int x2 = p3[0] - p1[0], y2 = p3[1] - p1[1];
ans = Math.max(ans, Math.abs(x1 * y2 - y1 * x2)); // 注意这里没有除以 2
}
}
}
return ans / 2.0;
}
}
class Solution {
public:
double largestTriangleArea(vector<vector<int>>& points) {
int n = points.size();
int ans = 0;
for (int i = 0; i < n - 2; i++) {
auto& p1 = points[i];
for (int j = i + 1; j < n - 1; j++) {
auto& p2 = points[j];
for (int k = j + 1; k < n; k++) {
auto& p3 = points[k];
int x1 = p2[0] - p1[0], y1 = p2[1] - p1[1];
int x2 = p3[0] - p1[0], y2 = p3[1] - p1[1];
ans = max(ans, abs(x1 * y2 - y1 * x2)); // 注意这里没有除以 2
}
}
}
return ans / 2.0;
}
};
func largestTriangleArea(points [][]int) float64 {
n := len(points)
ans := 0
for i := range n - 2 {
for j := i + 1; j < n-1; j++ {
for k := j + 1; k < n; k++ {
p1, p2, p3 := points[i], points[j], points[k]
x1, y1 := p2[0]-p1[0], p2[1]-p1[1]
x2, y2 := p3[0]-p1[0], p3[1]-p1[1]
ans = max(ans, abs(x1*y2-y1*x2)) // 注意这里没有除以 2
}
}
}
return float64(ans) / 2
}
func abs(x int) int { if x < 0 { return -x }; return x }
复杂度分析
- 时间复杂度：$\mathcal{O}(n^3)$，其中 $n$ 是 $\textit{points}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。
方法二：凸包 + 旋转卡壳
前置题目：587. 安装栅栏
若固定三角形的两个顶点，那么第三个顶点在哪？
三角形的高越长越好，所以第三个顶点相比在凸包内部，在凸包上更好（更远）。所以面积最大的三角形，三个顶点都在凸包上。
求出凸包后：
- 枚举凸包的顶点 $i$ 作为三角形的其中一个顶点。对于另外两个顶点，我们用旋转卡壳（同向双指针）计算。
- 初始化 $j=i+1$，$k=i+2$。
- 对于 $\triangle P_iP_jP_k$ 和 $\triangle P_iP_jP_{k+1}$ 的面积，如果后者更大，那么把 $k$ 加一。重复该过程，直到 $k+1$ 越界或者面积没有变大，跳出循环。
- 跳出循环后，$P_k$ 就移动到了一个在 $\overrightarrow{P_iP_j}$ 左侧且距离 $P_iP_j$ 最远的位置。计算 $\triangle P_iP_jP_k$ 的面积，更新答案的最大值。然后把 $j$ 加一，执行第三步。读者可以在纸上画画，随着 $j$ 的增大，在 $\overrightarrow{P_iP_j}$ 左侧且距离 $P_iP_j$ 最远的 $P_k$ 的下标 $k$ 也在增大，所以可以用同向双指针。
下面代码保证计算 $\mathbf{a} \times \mathbf{b}$ 时，$\mathbf{b}$ 在 $\mathbf{a}$ 的左侧，此时算出来的面积一定大于 $0$，无需取绝对值。
def det(x1: int, y1: int, x2: int, y2: int) -> int:
return x1 * y2 - y1 * x2
def convex_hull(points: List[List[int]]) -> List[List[int]]:
points.sort()
# 计算下凸包（从左到右）
q = []
for p in points:
while len(q) > 1 and det(q[-1][0] - q[-2][0], q[-1][1] - q[-2][1], p[0] - q[-1][0], p[1] - q[-1][1]) <= 0:
q.pop()
q.append(p)
# 计算上凸包（从右到左）
down_size = len(q)
# 注意下凸包的最后一个点，是上凸包的右边第一个点，所以从 n-2 开始遍历
for i in range(len(points) - 2, -1, -1):
p = points[i]
while len(q) > down_size and det(q[-1][0] - q[-2][0], q[-1][1] - q[-2][1], p[0] - q[-1][0], p[1] - q[-1][1]) <= 0:
q.pop()
q.append(p)
# 此时首尾是同一个点 points[0]，需要去掉
q.pop()
return q
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
ch = convex_hull(points)
def area(i: int, j: int, k: int) -> int:
return det(ch[j][0] - ch[i][0], ch[j][1] - ch[i][1], ch[k][0] - ch[i][0], ch[k][1] - ch[i][1])
m = len(ch)
ans = 0
# 固定三角形的其中一个顶点 ch[i]
for i in range(m):
# 同向双指针
k = i + 2
for j in range(i + 1, m - 1):
while k + 1 < m and area(i, j, k) < area(i, j, k + 1):
k += 1
# 循环结束后，ch[k] 距离 ch[i]ch[j] 最远
ans = max(ans, area(i, j, k)) # 注意这里没有除以 2
return ans / 2
class Solution {
public double largestTriangleArea(int[][] points) {
List<int[]> ch = convexHull(points);
int m = ch.size();
int ans = 0;
// 固定三角形的其中一个顶点 ch[i]
for (int i = 0; i < m; i++) {
// 同向双指针
int k = i + 2;
for (int j = i + 1; j < m - 1; j++) {
while (k + 1 < m && area(ch, i, j, k) < area(ch, i, j, k + 1)) {
k++;
}
// 循环结束后，ch[k] 距离 ch[i]ch[j] 最远
ans = Math.max(ans, area(ch, i, j, k)); // 注意这里没有除以 2
}
}
return ans / 2.0;
}
private List<int[]> convexHull(int[][] points) {
Arrays.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
// 计算下凸包（从左到右）
List<int[]> q = new ArrayList<>();
for (int[] p : points) {
while (q.size() > 1) {
int[] p1 = q.get(q.size() - 2);
int[] p2 = q.getLast();
if (det(p2[0] - p1[0], p2[1] - p1[1], p[0] - p2[0], p[1] - p2[1]) > 0) {
break;
}
q.removeLast();
}
q.add(p);
}
// 计算上凸包（从右到左）
int downSize = q.size();
// 注意下凸包的最后一个点，是上凸包的右边第一个点，所以从 n-2 开始遍历
for (int i = points.length - 2; i >= 0; i--) {
int[] p = points[i];
while (q.size() > downSize) {
int[] p1 = q.get(q.size() - 2);
int[] p2 = q.getLast();
if (det(p2[0] - p1[0], p2[1] - p1[1], p[0] - p2[0], p[1] - p2[1]) > 0) {
break;
}
q.removeLast();
}
q.add(p);
}
// 此时首尾是同一个点 points[0]，需要去掉
q.removeLast();
return q;
}
private int det(int x1, int y1, int x2, int y2) {
return x1 * y2 - y1 * x2;
}
private int area(List<int[]> ch, int i, int j, int k) {
return det(ch.get(j)[0] - ch.get(i)[0], ch.get(j)[1] - ch.get(i)[1],
ch.get(k)[0] - ch.get(i)[0], ch.get(k)[1] - ch.get(i)[1]);
}
}
struct Vec {
int x, y;
Vec sub(const Vec& b) const {
return {x - b.x, y - b.y};
}
int det(const Vec& b) const {
return x * b.y - y * b.x;
}
};
class Solution {
vector<Vec> convexHull(vector<Vec>& points) {
ranges::sort(points, {}, [](auto& p) { return pair(p.x, p.y); });
vector<Vec> q;
// 计算下凸包（从左到右）
for (auto& p : points) {
while (q.size() > 1 && q[q.size() - 1].sub(q[q.size() - 2]).det(p.sub(q[q.size() - 1])) <= 0) {
q.pop_back();
}
q.push_back(p);
}
// 计算上凸包（从右到左）
int down_size = q.size();
// 注意下凸包的最后一个点，是上凸包的右边第一个点，所以从 n-2 开始遍历
for (int i = (int) points.size() - 2; i >= 0; i--) {
auto& p = points[i];
while (q.size() > down_size && q[q.size() - 1].sub(q[q.size() - 2]).det(p.sub(q[q.size() - 1])) <= 0) {
q.pop_back();
}
q.push_back(p);
}
// 此时首尾是同一个点 points[0]，需要去掉
q.pop_back();
return q;
}
public:
double largestTriangleArea(vector<vector<int>>& points) {
vector<Vec> a(points.size());
for (int i = 0; i < points.size(); i++) {
a[i] = {points[i][0], points[i][1]};
}
vector<Vec> ch = convexHull(a);
auto area = [&](int i, int j, int k) -> int {
return ch[j].sub(ch[i]).det(ch[k].sub(ch[i]));
};
int m = ch.size();
int ans = 0;
// 固定三角形的其中一个顶点 ch[i]
for (int i = 0; i < m; i++) {
// 同向双指针
int k = i + 2;
for (int j = i + 1; j < m - 1; j++) {
while (k + 1 < m && area(i, j, k) < area(i, j, k + 1)) {
k++;
}
// 循环结束后，ch[k] 距离 ch[i]ch[j] 最远
ans = max(ans, area(i, j, k)); // 注意这里没有除以 2
}
}
return ans / 2.0;
}
};
type vec struct{ x, y int }
func (a vec) sub(b vec) vec { return vec{a.x - b.x, a.y - b.y} }
func (a vec) det(b vec) int { return a.x*b.y - a.y*b.x }
func convexHull(points []vec) (q []vec) {
slices.SortFunc(points, func(a, b vec) int { return cmp.Or(a.x-b.x, a.y-b.y) })
// 计算下凸包（从左到右）
for _, p := range points {
for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) <= 0 {
q = q[:len(q)-1]
}
q = append(q, p)
}
// 计算上凸包（从右到左）
downSize := len(q)
// 注意下凸包的最后一个点，是上凸包的右边第一个点，所以从 n-2 开始遍历
for i := len(points) - 2; i >= 0; i-- {
p := points[i]
for len(q) > downSize && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) <= 0 {
q = q[:len(q)-1]
}
q = append(q, p)
}
// 此时首尾是同一个点 points[0]，需要去掉
q = q[:len(q)-1]
return
}
func largestTriangleArea(points [][]int) float64 {
a := make([]vec, len(points))
for i, p := range points {
a[i] = vec{p[0], p[1]}
}
ch := convexHull(a)
area := func(i, j, k int) int {
return ch[j].sub(ch[i]).det(ch[k].sub(ch[i]))
}
m := len(ch)
ans := 0
// 固定三角形的其中一个顶点 ch[i]
for i := range ch {
// 同向双指针
k := i + 2
for j := i + 1; j < m-1; j++ {
for k+1 < m && area(i, j, k) < area(i, j, k+1) {
k++
}
// 循环结束后，ch[k] 距离 ch[i]ch[j] 最远
ans = max(ans, area(i, j, k)) // 注意这里没有除以 2
}
}
return float64(ans) / 2
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $\textit{points}$ 的长度。枚举 $i$ 是 $\mathcal{O}(n)$，枚举 $j$ 和 $k$ 的同向双指针也是 $\mathcal{O}(n)$。
- 空间复杂度：$\mathcal{O}(n)$。
注：本题有 $\mathcal{O}(n)$ 做法，见论文 Maximal Area Triangles in a Convex Polygon。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
