[LeetCode] Challenge log 812

Posted on | Edited on |
812. Largest Triangle Area

Violent full traverse solution.

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

1
2
3
4
5
Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

img

Notes:

  • 3 <= points.length <= 50.
  • No points will be duplicated.
  • -50 <= points[i][j] <= 50.
  • Answers within 10^-6 of the true value will be accepted as correct.
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        res = 0
        n = len(points)
        
        def area(p, q, r):
            return .5 * abs(p[0]*q[1]+q[0]*r[1]+r[0]*p[1]
                           -p[1]*q[0]-q[1]*r[0]-r[1]*p[0])
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1 , n):
                    res = max(res, area(points[i], points[j], points[k]))
        
        return res
0%