leetcode-812-Largest Triangle Area

chenjx85

发布于 2018-05-21 18:18:34

8610

发布于 2018-05-21 18:18:34

题目描述：

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.

要完成的函数：

double largestTriangleArea(vector<vector<int>>& points)

说明：

1、这道题给定所有点的坐标，要在这些点中间构建一个面积最大的三角形，最后返回这个三角形的面积。

2、这道题最开始想着，能不能直接找到这三个点，最后返回面积就好了。

但很快就发现，通过寻找距离圆心最远的点 i ，可以找到这个面积最大的三角形中的一个点。

但其余两个点就不知道能怎样找到。距离点 i 最远的一个点作为第二个点？好像不太对。

最后还是在暴力法下屈服了……

三角形的面积公式是：

已知三个点为(x1,y1)，(x2,y2)，(x3,y3)

面积为A= 1/2 * [ x1(y2-y3) + x2(y3-y1) + x3(y1-y2) ]

代码如下，分享给大家：

    double largestTriangleArea(vector<vector<int>>& points)
    {
        int s1=points.size();
        double res=0;
        double area;
        for(int i=0;i<s1;i++)
        {
            for(int j=i+1;j<s1;j++)
            {
                for(int k=j+1;k<s1;k++)
                {
                    area=0.5*abs(points[i][0]*(points[j][1]-points[k][1])+points[j][0]*(points[k][1]-points[i][1])+points[k][0]*(points[i][1]-points[j][1]));
                    res=max(res,area);
                }
            }
        }
        return res;
    }

上述代码时间复杂度为O(n^3)，实测7ms，没有百分比，因为网站提示当前提交量还不够多。

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-05-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

area