LeetCode 812. 最大三角形面积
题目描述
题意分析
从给定平面点中选择三个不同的点，求它们能组成的最大三角形面积。边可以朝任意方向，不要求平行于坐标轴；共线的三点面积为零。
点数最多为
50，可以直接枚举所有三点组合。关键是用常数时间准确算出每个三角形的面积，不必额外求边长、高或角度。
解法：枚举三点 + 叉积
核心思路
[!blue]
选定三点
A、B、C，以A为共同起点，构造向量AB = (x1, y1)和AC = (x2, y2)。二维叉积是cross = x1 * y2 - x2 * y1，其绝对值等于这两个向量围成的平行四边形面积；三角形恰好占其中一半，所以面积为abs(cross) / 2。叉积的正负只反映两个向量的方向顺序。交换
B、C会让符号反转，但三角形面积不变，因此要取绝对值；三点共线时，两向量成比例，叉积自然为零，不需要另作共线判断。按
i < j < k枚举下标，每个无序三点组合都有且只有一种这样的排列，所以所有候选三角形都会被检查一次。best从零开始，每次与当前面积比较并保留较大值，枚举结束后就是最大面积。坐标是整数，可以先在整数域计算叉积，最后才用
2.0做浮点除法。叉积绝对值可能为奇数，若先进行整数除法再转浮点，就会丢掉半单位面积。Go 同样先把叉积转换为float64，再除以2.0。
解题步骤
- 按 i<j<k 枚举不同三点。
- 计算两向量叉积，取绝对值再除二。
- 维护最大面积。
题目坐标范围为
[-50, 50]，坐标差绝对值不超过100，叉积的两项乘积及相减结果都能安全存入int。只有三个点时只计算一次；全部点共线时所有候选面积为零，返回初始的零面积。
代码实现
class Solution {
public double largestTriangleArea(int[][] points) {
double best = 0.0;
int n = points.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
double area = area(points[i], points[j], points[k]);
if (area > best) {
best = area;
}
}
}
}
return best;
}
private double area(int[] a, int[] b, int[] c) {
// 两个向量使用同一个基点，叉积绝对值为面积的两倍
int x1 = b[0] - a[0];
int y1 = b[1] - a[1];
int x2 = c[0] - a[0];
int y2 = c[1] - a[1];
// 最后使用浮点除法，保留半单位面积
return Math.abs(x1 * y2 - x2 * y1) / 2.0;
}
}
func largestTriangleArea(points [][]int) float64 {
best := 0.0
n := len(points)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
area := triangleArea(points[i], points[j], points[k])
if area > best {
best = area
}
}
}
}
return best
}
func triangleArea(a []int, b []int, c []int) float64 {
// 两个向量使用同一个基点，叉积绝对值为面积的两倍
x1 := b[0] - a[0]
y1 := b[1] - a[1]
x2 := c[0] - a[0]
y2 := c[1] - a[1]
cross := x1*y2 - x2*y1
if cross < 0 {
cross = -cross
}
// 最后使用浮点除法，保留半单位面积
return float64(cross) / 2.0
}
复杂度分析
- 时间复杂度：$O(n^3)$，每组三点常数计算。
- 空间复杂度：$O(1)$，不保存中间图形。
关键点总结
[!green]
- 叉积符号表示方向，面积只取大小。
- 枚举下标递增，避免同一三点组合重复处理。
易错点总结
[!yellow]
- 整除二会丢掉0.5部分。
- 不取绝对值，会让负方向面积无法更新最大值。
- 把叉积两项相减写成相加，会改变面积公式。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 叉积既能判断共线，也能给出三点组成三角形的两倍有向面积。 |
| 补充题 19. 判断一个点是否在三角形内 | 中等 | 三角形面积或叉积符号是点内外判断的基础，本题枚举三点并取面积最大值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！