题目

对于给定的点集，求出一个最大三角形的面积。

我的代码 （效率极低）

代码思路： 对于点集进行组合（不重复），然后对组合的点集进行计算。使用海伦公式。

import itertools
import math
class Solution(object):
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        maxarea=0
        Tpoints=itertools.combinations(points,3)
        i=0
        for Tpoint in Tpoints:
            a=math.sqrt((Tpoint[0][0]-Tpoint[1][0])**2+(Tpoint[0][1]-Tpoint[1][1])**2)
            b=math.sqrt((Tpoint[1][0]-Tpoint[2][0])**2+(Tpoint[1][1]-Tpoint[2][1])**2)
            c=math.sqrt((Tpoint[0][0]-Tpoint[2][0])**2+(Tpoint[0][1]-Tpoint[2][1])**2)
            p=(a+b+c)/2
            if p<max(a,b,c)+0.01:
                continue
            area=math.sqrt(p*(p-a)*(p-b)*(p-c))
            if area>maxarea:
                maxarea=area
        return maxarea

高效代码

**代码思路差异：**使用了三层的循环，i-j-k， 使用了新的计算公式。

s = 0.5 * abs(x2 * y3 + x3 * y1 + x1 * y2 - x3 * y2 - x1 * y3 - x2 * y1)
详情更多可自行搜索多边形面积计算之类。

class Solution(object):
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        maxyet = 0
        n = len(points)
        for i in range(n): 
            x1, y1 = points[i]
            for j in range(i+1, n): 
                x2, y2 = points[j]
                for k in range(j+1, n): 
                    x3, y3 = points[k]
                    s = 0.5 * abs(x2 * y3 + x3 * y1 + x1 * y2 - x3 * y2 - x1 * y3 - x2 * y1)
                    if s > maxyet: 
                        maxyet = s
        return maxyet