算法题 最大三角形面积

最大三角形面积

问题描述

给定包含n个点的数组points，其中points[i] = [xi, yi]表示平面上的一个点。
返回由其中任意三个点组成的三角形的最大面积。

示例：

输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出: 2.00000 解释: 选择点 [0,2], [2,0], [0,0] 组成的三角形面积最大，为 2。

算法思路

核心：

1. 三角形面积公式：给定三个点 A(x₁,y₁), B(x₂,y₂), C(x₃,y₃)，三角形面积为：

   Area = 0.5 × |x₁(y₂ - y₃) + x₂(y₃ - y₁) + x₃(y₁ - y₂)|

   这是叉积公式的简化形式。

2. 暴力枚举：

   • 3 <= points.length <= 50
   • 三重循环的时间复杂度：O(n³) = 50³ = 125,000，可以接受

3. 优化：

   • 可以使用凸包算法（Andrew算法）先求凸包，然后在凸包上找最大三角形
   • 对于 n ≤ 50 的小数据，暴力更简单

方法：

• 暴力三重循环：枚举所有可能的三点组合，计算面积并记录最大值
• 凸包：对于大数据集更优

代码实现

方法一：暴力枚举

classSolution{/** * 使用暴力枚举找到最大三角形面积 * * @param points 点的坐标数组，points[i] = [x, y] * @return 最大三角形面积 */publicdoublelargestTriangleArea(int[][]points){intn=points.length;doublemaxArea=0.0;// 三重循环枚举所有三点组合for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){for(intk=j+1;k<n;k++){// 计算三角形面积doublearea=calculateTriangleArea(points[i][0],points[i][1],points[j][0],points[j][1],points[k][0],points[k][1]);maxArea=Math.max(maxArea,area);}}}returnmaxArea;}/** * 使用叉积公式计算三角形面积 * * @param x1, y1 第一个点的坐标 * @param x2, y2 第二个点的坐标 * @param x3, y3 第三个点的坐标 * @return 三角形面积 */privatedoublecalculateTriangleArea(intx1,inty1,intx2,inty2,intx3,inty3){// 叉积公式：Area = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|doublearea=0.5*Math.abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));returnarea;}}

方法二：向量叉积

classSolution{/** * 使用向量叉积计算面积 * 将三角形看作两个向量的叉积 */publicdoublelargestTriangleArea(int[][]points){intn=points.length;doublemaxArea=0.0;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){for(intk=j+1;k<n;k++){// 以points[i]为原点，构造两个向量int[]vector1={points[j][0]-points[i][0],points[j][1]-points[i][1]};int[]vector2={points[k][0]-points[i][0],points[k][1]-points[i][1]};// 叉积的绝对值的一半就是面积doublearea=0.5*Math.abs(vector1[0]*vector2[1]-vector1[1]*vector2[0]);maxArea=Math.max(maxArea,area);}}}returnmaxArea;}}

方法三：凸包

importjava.util.*;classSolution{/** * 使用凸包：最大面积三角形的三个顶点一定在凸包上 */publicdoublelargestTriangleArea(int[][]points){// 先计算凸包int[][]convexHull=computeConvexHull(points);intn=convexHull.length;// 如果凸包点数小于3，无法构成三角形if(n<3){return0.0;}doublemaxArea=0.0;// 在凸包上暴力枚举for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){for(intk=j+1;k<n;k++){doublearea=calculateTriangleArea(convexHull[i][0],convexHull[i][1],convexHull[j][0],convexHull[j][1],convexHull[k][0],convexHull[k][1]);maxArea=Math.max(maxArea,area);}}}returnmaxArea;}/** * 使用Andrew算法计算凸包 */privateint[][]computeConvexHull(int[][]points){intn=points.length;if(n<=1)returnpoints;// 按x坐标排序，x相同时按y排序Arrays.sort(points,(a,b)->{if(a[0]!=b[0])returna[0]-b[0];returna[1]-b[1];});List<int[]>hull=newArrayList<>();// 构建下凸包for(inti=0;i<n;i++){while(hull.size()>=2&&cross(hull.get(hull.size()-2),hull.get(hull.size()-1),points[i])<=0){hull.remove(hull.size()-1);}hull.add(points[i]);}// 构建上凸包intlowerSize=hull.size();for(inti=n-2;i>=0;i--){while(hull.size()>lowerSize&&cross(hull.get(hull.size()-2),hull.get(hull.size()-1),points[i])<=0){hull.remove(hull.size()-1);}hull.add(points[i]);}// 移除重复的起点（如果凸包点数>1）if(hull.size()>1){hull.remove(hull.size()-1);}returnhull.toArray(newint[0][]);}/** * 计算叉积：(p2 - p1) × (p3 - p1) */privatelongcross(int[]p1,int[]p2,int[]p3){return(long)(p2[0]-p1[0])*(p3[1]-p1[1])-(long)(p2[1]-p1[1])*(p3[0]-p1[0]);}privatedoublecalculateTriangleArea(intx1,inty1,intx2,inty2,intx3,inty3){return0.5*Math.abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));}}

算法分析

• 时间复杂度：

  • 暴力：O(n³)，n ≤ 50
  • 凸包：O(n log n + h³)，h是凸包点数

• 空间复杂度：

  • 暴力：O(1)
  • 凸包：O(n) - 存储凸包点

算法过程

1：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]

三点组合：

1. [0,0], [0,2], [2,0]：

   • 面积 = 0.5 × |0×(2-0) + 0×(0-0) + 2×(0-2)|
   • = 0.5 × |0 + 0 + 2×(-2)| = 0.5 × 4 = 2.0

2. [0,0], [0,1], [1,0]：

   • 面积 = 0.5 × |0×(1-0) + 0×(0-0) + 1×(0-1)| = 0.5 × 1 = 0.5

3. [0,1], [0,2], [2,0]：

   • 面积 = 0.5 × |0×(2-0) + 0×(0-1) + 2×(1-2)| = 0.5 × 2 = 1.0

最大面积：2.0

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]points1={{0,0},{0,1},{1,0},{0,2},{2,0}};System.out.printf("Test 1: %.5f\n",solution.largestTriangleArea(points1));// 2.00000// 测试用例2：等边三角形int[][]points2={{0,0},{1,0},{0,1}};System.out.printf("Test 2: %.5f\n",solution.largestTriangleArea(points2));// 0.50000// 测试用例3：三点共线（面积为0）int[][]points3={{0,0},{1,1},{2,2}};System.out.printf("Test 3: %.5f\n",solution.largestTriangleArea(points3));// 0.00000// 测试用例4：正方形的四个顶点int[][]points4={{0,0},{0,1},{1,1},{1,0}};System.out.printf("Test 4: %.5f\n",solution.largestTriangleArea(points4));// 0.50000// 测试用例5：最小情况（正好3个点）int[][]points5={{0,0},{3,0},{0,4}};System.out.printf("Test 5: %.5f\n",solution.largestTriangleArea(points5));// 6.00000// 测试用例6：包含负坐标int[][]points6={{-1,-1},{1,1},{0,2}};System.out.printf("Test 6: %.5f\n",solution.largestTriangleArea(points6));// 2.00000// 测试用例7：大坐标值int[][]points7={{0,0},{100,0},{0,100}};System.out.printf("Test 7: %.5f\n",solution.largestTriangleArea(points7));// 5000.00000// 测试用例8：多个点但最大三角形由特定三点构成int[][]points8={{0,0},{1,1},{2,2},{3,0},{0,3}};System.out.printf("Test 8: %.5f\n",solution.largestTriangleArea(points8));// 4.50000// 测试用例9：所有点都在一个圆上（正多边形）int[][]points9={{1,0},{0,1},{-1,0},{0,-1}};System.out.printf("Test 9: %.5f\n",solution.largestTriangleArea(points9));// 1.00000// 测试用例10：边界情况 - 重复点int[][]points10={{0,0},{0,0},{1,0},{0,1}};System.out.printf("Test 10: %.5f\n",solution.largestTriangleArea(points10));// 0.50000}

关键点

1. 面积公式：

   • 叉积公式最稳定，避免了浮点运算误差
   • 不需要计算边长或角度，直接使用坐标

2. 绝对值：

   • 叉积可能为负（取决于点的顺序）
   • 取绝对值确保面积为正

3. 三点共线：

   • 叉积为0时，三点共线，面积为0

常见问题

1. 为什么最大三角形的顶点一定在凸包上？

   • 这是一个几何定理：给定平面上的点集，面积最大的三角形的三个顶点必定在点集的凸包上
   • 因为如果有一个顶点在凸包内部，可以向外移动到凸包边界，面积会增大

2. 叉积公式？

   • 基于向量叉积的几何意义：|a × b| = |a||b|sinθ
   • 三角形面积 = 0.5 × |a||b|sinθ = 0.5 × |a × b|