## Description

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.

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. 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.

## Solutions

### 1. Backtracking

# Time: O(nlogn)
# Space: O(n)
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
if not points or len(points) <= 2:
return 0
res = [-1]
self.dfs(points, 0, [], res)
return res

def dfs(self, points, start, path, res):
if path and len(path) >= 3:
s = 0.5 * abs(path * path + path * path + path * path - path * path -  path * path - path * path)
res = max(s, res)
return
n = len(points)
for i in range(start, n):
self.dfs(points, i+1, path+[points[i]], res)
# 57/57 cases passed (268 ms)
# Your runtime beats 29.53 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


### 2. Math

class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
return max(0.5 * abs(i * j + j * k + k * i- j * i - k * j - i * k)
for i, j, k in itertools.combinations(points, 3))
# 57/57 cases passed (136 ms)
# Your runtime beats 77.17 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)