812. Largest Triangle Area | Easy
Day 2 post. May revisit in the future to come up with more efficient 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.
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.
class Solution:
def largestTriangleArea(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
# # initial approach - if any two points
# # are on same axis this works
# x_max = max([ x[0] for x in points ])
# x_min = min([ x[0] for x in points ])
# y_max = max([ x[1] for x in points ])
# y_min = min([ x[1] for x in points ])
# return 0.5*(x_max-x_min)*(y_max-y_min)
# ---------------
# # second approach - naive double loops - weird rounding error!!!
# def area(pt1, pt2, pt3):
# a = round(((pt1[1]-pt2[1])**2 + (pt1[0]-pt2[0])**2)**0.5, 6)
# b = round(((pt2[1]-pt3[1])**2 + (pt2[0]-pt3[0])**2)**0.5, 6)
# c = round(((pt3[1]-pt1[1])**2 + (pt3[0]-pt1[0])**2)**0.5, 6)
# s = round((a+b+c)/2, 6)
# if s < a or s < b or s < c:
# print (a, b, c, s)
# return (s*(s-a)*(s-b)*(s-c))**0.5
# maxarea = 0.0
# for point1 in points[:-2]:
# for point2 in points[1:-1]:
# for point3 in points[2:]:
# _area = area(point1, point2, point3)
# if _area > maxarea:
# maxarea = _area
# return maxarea
# --------------
# third attempt - time limit exceeds???
def area(pt1, pt2, pt3):
a = ((pt1[1]-pt2[1])**2 + (pt1[0]-pt2[0])**2)**0.5
b = ((pt2[1]-pt3[1])**2 + (pt2[0]-pt3[0])**2)**0.5
c = ((pt3[1]-pt1[1])**2 + (pt3[0]-pt1[0])**2)**0.5
return (a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)/16
# maxarea = 0.0
# for point1 in points[:-2]:
# for point2 in points[1:-1]:
# for point3 in points[2:]:
# _area = area(point1, point2, point3)
# if _area > maxarea:
# maxarea = _area
# return maxarea**0.5
# ----------------
# frustrated attempt 4 - very fast but inaccurate
# xarr = enumerate([ x[0] for x in points ])
# _xarr = enumerate([ x[0] for x in points ])
# yarr = enumerate([ x[1] for x in points ])
# _yarr = enumerate([ x[1] for x in points ])
# x_max = max(xarr, key=lambda x:x[1])[0]
# x_min = min(_xarr, key=lambda x:x[1])[0]
# y_max = max(yarr, key=lambda x:x[1])[0]
# y_min = min(_yarr, key=lambda x:x[1])[0]
# points = [points[x_max], points[x_min], points[y_max], points[y_min]]
# maxarea = 0.0
# for point1 in points[:-2]:
# for point2 in points[1:-1]:
# for point3 in points[2:]:
# _area = area(point1, point2, point3)
# if _area > maxarea:
# maxarea = _area
# return maxarea**0.5
maxarea = 0.0
for i in range(0, len(points)-2):
for j in range(i, len(points)-1):
for k in range(j, len(points)):
_area = area(points[i], points[j], points[k])
if _area > maxarea:
maxarea = _area
return maxarea**0.5
Initial runtime:
Runtime: 756 ms, faster than 13.43% of Python3 online submissions for Largest Triangle Area.
Changed triangle area calculation to this and did better.
def area(pt1, pt2, pt3):
return abs(( pt1[0]*(pt2[1]-pt3[1]) + pt2[0]*(pt3[1]-pt1[1]) + pt3[0]*(pt1[1]-pt2[1]) )/2)
Runtime: 236 ms, faster than 43.28% of Python3 online submissions for Largest Triangle Area.