題目描述
給定包含多個點的集合，從其中取三個點組成三角形，回傳能組成的最大三角形的面積，
示例
示例:
輸入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
輸出: 2
解釋:
這五個點如下圖所示，組成的橙色三角形是最大的，面積為2，
注意
3 <= points.length <= 50.
不存在重復的點，
-50 <= points[i][j] <= 50.
結果誤差值在 10^-6 以內都認為是正確答案，
解題思路
暴力解題：已知三點坐標，求三角形面積，回傳最大面積
計算方法
1：海倫公式
2：向量法
代碼
//海倫公式
double getLength(int *point1,int *point2){
return sqrt( (point1[0]-point2[0])*(point1[0]-point2[0]) +
(point1[1]-point2[1])*(point1[1]-point2[1])
);
}
/*
向量法S = 0.5 * |A * B|= 0.5 * |X1Y2 + X2Y3 + X3Y1 -X2Y1 -X3Y2 -X1Y3|
double getArea(int *point1, int *point2, int *point3){
return 0.5 * abs(point1[0]*ppoint2[1] + point2[0]*point3[1] + point3[0]*point1[1]
- point2[0]*point1[1] - point3[0]*point2[1] -point1[0]*point3[1]);
}
*/
double largestTriangleArea(int** points, int pointsSize, int* pointsColSize){
int i,j,k;
double a;
double b;
double c;
double p;
double s;
double ret=0;
for(i = 0; i < pointsSize - 2; i++) {
for(j = i + 1; j < pointsSize - 1; j++) {
for(k = j + 1; k < pointsSize; k++) {
a = getLength(points[i],points[j]);
b = getLength(points[i],points[k]);
c = getLength(points[k],points[j]);
p = (a+b+c)/2;
s = sqrt(p*(p-a)*(p-b)*(p-c));
//s=getArea(points[i], points[j], points[k]);
ret = s > ret? s:ret;
}
}
}
return ret;
}
鏈接
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252227.html
標籤：其他
上一篇：谷粒學院專案總結