题目
给你一个由 X-Y 平面上的点组成的数组 points ,其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形,返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。
示例 1:
![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/80fd8429088f6d747d88e2b30d2283de.png#pic_center)
输入:points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出:2.00000
解释:输入中的 5 个点如上图所示,红色的三角形面积最大。
示例 2:
输入:points = [[1,0],[0,0],[0,1]]
输出:0.50000
提示:
3 <= points.length <= 50
-50 <= xi, yi <= 50
给出的所有点 互不相同
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/largest-triangle-area
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解思路
- 记住行列式公式
∣
x
1
y
1
1
x
2
y
2
1
x
3
y
3
1
∣
\left| \begin{array}{cccc} x1 & y1 & 1 \\ x2 & y2 & 1\\ x3 & y3 & 1 \end{array} \right|
x1x2x3y1y2y3111
代码
class Solution {
public:
double triangleArea(int x1,int y1,int x2,int y2,int x3,int y3)
{
return 0.5*abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2);
}
double largestTriangleArea(vector<vector<int>>& points) {
double ret = 0;
int n = points.size();
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
ret = max(ret,triangleArea(points[i][0],points[i][1],
points[j][0],points[j][1],points[k][0],points[k][1]));
}
}
}
return ret;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)