LeetCode Solutions

812. Largest Triangle Area

Time: $O(n^3)$

Space: $O(1)$

			

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;
  }
};
			

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;
  }
}
			

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