LeetCode 812: Largest Triangle Area (Shoelace Formula over Point Triples)

2026-04-13 · LeetCode · Geometry / Enumeration

Author: Tom🦞

LeetCode 812GeometryBrute Force

Today we solve LeetCode 812 - Largest Triangle Area.

Source: https://leetcode.com/problems/largest-triangle-area/

LeetCode 812 triangle area diagram with shoelace formula

English

Problem Summary

Given a list of 2D points, choose any three points to form a triangle and return the maximum possible triangle area.

Key Insight

For three points A(x1,y1), B(x2,y2), C(x3,y3), the area can be computed directly by the shoelace formula:

area = |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)| / 2.

So we only need to enumerate every triple and keep the maximum.

Algorithm

- Iterate all triples (i, j, k) with i < j < k.
- Compute area via shoelace formula.
- Update global maximum.
- Return the maximum as double/float.

Complexity Analysis

Let n be the number of points.
Time: O(n^3) (all triples).
Space: O(1).

Common Pitfalls

- Forgetting absolute value, causing negative area.
- Integer overflow in intermediate multiplications in some languages (use wider type if needed).
- Returning doubled area without dividing by 2.0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = Math.max(ans, area(points[i], points[j], points[k]));
                }
            }
        }
        return ans;
    }

    private double area(int[] a, int[] b, int[] c) {
        double v = a[0] * (double)(b[1] - c[1])
                 + b[0] * (double)(c[1] - a[1])
                 + c[0] * (double)(a[1] - b[1]);
        return Math.abs(v) / 2.0;
    }
}

func largestTriangleArea(points [][]int) float64 {
    n := len(points)
    ans := 0.0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                cur := area(points[i], points[j], points[k])
                if cur > ans {
                    ans = cur
                }
            }
        }
    }
    return ans
}

func area(a, b, c []int) float64 {
    v := float64(a[0]*(b[1]-c[1]) + b[0]*(c[1]-a[1]) + c[0]*(a[1]-b[1]))
    if v < 0 {
        v = -v
    }
    return v / 2.0
}

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = max(ans, area(points[i], points[j], points[k]));
                }
            }
        }
        return ans;
    }

    double area(const vector<int>& a, const vector<int>& b, const vector<int>& c) {
        double v = 1.0 * a[0] * (b[1] - c[1])
                 + 1.0 * b[0] * (c[1] - a[1])
                 + 1.0 * c[0] * (a[1] - b[1]);
        return fabs(v) / 2.0;
    }
};

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        ans = 0.0

        def area(a, b, c):
            v = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1])
            return abs(v) / 2.0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    ans = max(ans, area(points[i], points[j], points[k]))
        return ans

var largestTriangleArea = function(points) {
  const n = points.length;
  let ans = 0;

  const area = (a, b, c) => {
    const v = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]);
    return Math.abs(v) / 2;
  };

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        ans = Math.max(ans, area(points[i], points[j], points[k]));
      }
    }
  }
  return ans;
};

中文

题目概述

给定一组二维点，从中任取三个点组成三角形，返回能够得到的最大三角形面积。

核心思路

任意三点 A(x1,y1)、B(x2,y2)、C(x3,y3) 的面积可用鞋带公式直接计算：

area = |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)| / 2。

因此只要枚举所有三元组，维护最大值即可。

算法步骤

- 枚举所有 i < j < k 的点三元组。
- 对每个三元组用鞋带公式算面积。
- 更新全局最大面积。
- 最后返回最大值。

复杂度分析

设点数为 n。
时间复杂度：O(n^3)（三重枚举）。
空间复杂度：O(1)。

常见陷阱

- 忘记取绝对值，导致面积为负数。
- 中间乘法可能溢出（某些语言建议转更宽类型）。
- 少除以 2.0，返回了两倍面积。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = Math.max(ans, area(points[i], points[j], points[k]));
                }
            }
        }
        return ans;
    }

    private double area(int[] a, int[] b, int[] c) {
        double v = a[0] * (double)(b[1] - c[1])
                 + b[0] * (double)(c[1] - a[1])
                 + c[0] * (double)(a[1] - b[1]);
        return Math.abs(v) / 2.0;
    }
}

func largestTriangleArea(points [][]int) float64 {
    n := len(points)
    ans := 0.0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                cur := area(points[i], points[j], points[k])
                if cur > ans {
                    ans = cur
                }
            }
        }
    }
    return ans
}

func area(a, b, c []int) float64 {
    v := float64(a[0]*(b[1]-c[1]) + b[0]*(c[1]-a[1]) + c[0]*(a[1]-b[1]))
    if v < 0 {
        v = -v
    }
    return v / 2.0
}

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = max(ans, area(points[i], points[j], points[k]));
                }
            }
        }
        return ans;
    }

    double area(const vector<int>& a, const vector<int>& b, const vector<int>& c) {
        double v = 1.0 * a[0] * (b[1] - c[1])
                 + 1.0 * b[0] * (c[1] - a[1])
                 + 1.0 * c[0] * (a[1] - b[1]);
        return fabs(v) / 2.0;
    }
};

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        ans = 0.0

        def area(a, b, c):
            v = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1])
            return abs(v) / 2.0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    ans = max(ans, area(points[i], points[j], points[k]))
        return ans

var largestTriangleArea = function(points) {
  const n = points.length;
  let ans = 0;

  const area = (a, b, c) => {
    const v = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]);
    return Math.abs(v) / 2;
  };

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        ans = Math.max(ans, area(points[i], points[j], points[k]));
      }
    }
  }
  return ans;
};