# Leetcode: Largest Triangle Area

Largest Triangle Area Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Related Reading: Shoelace formula in wikipedia

```## Blog link: https://code.dennyzhang.com/largest-triangle-area
## Basic Ideas:
##   Check whether 3 points can form a triangle
##        any 2 edges should be bigger than the 3rd one
##        Can't be in one line: k = (y2-y1)/(x2-x1)
##   Get area of a triangle from 3 edges
##        https://www.mathsisfun.com/geometry/herons-formula.html
##        s = (a+b+c)/2, area = sqrt(s*(s-a)*(s-b)*(s-c))
## Complexity: Time O(n*n*n) Space O(1)
class Solution:
def largestTriangleArea(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
from math import sqrt
def getArea(point1, point2, point3):
# get 3 edges
a = sqrt(pow((point1-point2), 2) + pow((point1-point2), 2))
b = sqrt(pow((point1-point3), 2) + pow((point1-point3), 2))
c = sqrt(pow((point2-point3), 2) + pow((point2-point3), 2))
# same point
if 0 in [a, b, c]: return 0

# valid edges
if a+b<=c or a+c<=b or b+c<=a: return 0

# check whether 3 points in the same line
if point1-point2 == 0:
k1 = None
else:
k1 = (point1-point2)/(point1-point2)

if point1-point3 == 0:
k2 = None
else:
k2 = (point1-point3)/(point1-point3)

if point2-point3 == 0:
k3 = None
else:
k3 = (point2-point3)/(point2-point3)

if len(set([k1, k2, k3])) != 3: return 0

# get area
s = (a+b+c)/2
area = sqrt(s*(s-a)*(s-b)*(s-c))
return area

res = 0
for i in range(len(points)-2):
for j in range(i+1, len(points)-1):
for k in range(j+1, len(points)):
res = max(res, getArea(points[i], points[j], points[k]))
return res
```

Share It, If You Like It.