leetcode-812-Largest Triangle Area

题目描述:

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,没有百分比,因为网站提示当前提交量还不够多。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q152 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) wh...

43370
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

602140
来自专栏Jack-Cui

Day7、Python

题目打印出如下图案(菱形) ? 1、程序分析     先把图形分成两部分来看待,前四行一个规律,后三行一个规律,利用双重for循环,第一层控制行...

22900
来自专栏chenjx85的技术专栏

leetcode-77-组合

vector<vector<int>> combine(int n, int k) 

17710
来自专栏王肖的UT

GLSL-内置函数

64630
来自专栏desperate633

LintCode 奇偶分割数组题目分析代码

8210
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

23330
来自专栏计算机视觉与深度学习基础

POJ2253 && ZOJ1942

两种写法 用floyd算法,求所有点之间的最大跳的最小值,最后输出a[0][1],即起始与终止位置的最小值,采用传递闭包的思路,时间复杂度较高,但代码简单。 或...

21790
来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

256100
来自专栏JasonhavenDai

快速学会LATEX数学符号和公式1.概念2.空白距离3.特殊字符$ % ^ & _ { } ~ \4. 数学公式5.参考

1.概念 LATEX 源文件的格式为普通的 ASCII 文件,你可以使用任何文本编辑器来创建。LATEX 源文件不仅包括你所要排版的文本,还包括 LATEX...

39280

扫码关注云+社区

领取腾讯云代金券