# 812. Largest Triangle Area 最大三角形面积

@TOC

## # 题目描述

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
"""
res = 0
N = len(points)
for i in range(N - 2):
for j in range(i + 1, N - 1):
for k in range(i + 2, N):
(x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k]
res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
return res
``````

### # 组合函数

python的组合公式实现了数学中的组合运算符，节省了代码量。

``````class Solution:
def largestTriangleArea(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
# S=(1/2)*(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)
def f(p1, p2, p3):
(x1, y1), (x2, y2), (x3, y3) = p1, p2, p3
return 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
return max(f(a, b, c) for a, b, c in itertools.combinations(points, 3))
``````

## # 日期

2018 年 4 月 9 日 —— 天气变好，春暖花开～～ 2018 年 11 月 ９ 日 —— 睡眠可以