Skip to content

812. Largest Triangle Area 👎

  • Time: $O(n^3)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  double largestTriangleArea(vector<vector<int>>& points) {
    double ans = 0;

    for (const vector<int>& A : points)
      for (const vector<int>& B : points)
        for (const vector<int>& C : points)
          ans = max(ans, 0.5 * abs((B[0] - A[0]) * (C[1] - A[1]) -
                                   (C[0] - A[0]) * (B[1] - A[1])));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public double largestTriangleArea(int[][] points) {
    double ans = 0;

    for (int[] A : points)
      for (int[] B : points)
        for (int[] C : points)
          ans = Math.max(ans, 0.5 * Math.abs((B[0] - A[0]) * (C[1] - A[1]) - //
                                             (C[0] - A[0]) * (B[1] - A[1])));

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def largestTriangleArea(self, points: List[List[int]]) -> float:
    ans = 0

    for Ax, Ay in points:
      for Bx, By in points:
        for Cx, Cy in points:
          ans = max(ans, 0.5 * abs((Bx - Ax) * (Cy - Ay) -
                                   (Cx - Ax) * (By - Ay)))

    return ans