LargestTriangleArea [source code]
public class LargestTriangleArea {
static
/******************************************************************************/
class Solution {
public double largestTriangleArea(int[][] points) {
int N = points.length;
double[][] distance = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j)
continue;
double cur_distance = Math.sqrt ((points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]));
distance[i][j] = distance[j][i] = cur_distance;
}
}
double max_area = 0.0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j == i)
continue;
for (int k = 0; k < N; k++) {
if (k == j || k == i)
continue;
max_area = Math.max (max_area, area (distance[i][j], distance[j][k], distance[k][i]));
}
}
}
return max_area;
}
double area (double a, double b, double c) {
if (!isTriangle (a, b, c))
return 0.0;
double s = 0.5 * (a + b + c);
double res = Math.sqrt (s * (s - a) * (s - b) * (s - c));
return res;
}
boolean isTriangle (double a, double b, double c) {
return a + b > c && b + c > a && a + c > b;
}
}
/******************************************************************************/
public static void main(String[] args) {
LargestTriangleArea.Solution tester = new LargestTriangleArea.Solution();
int[][][] inputs = {
{{0,0},{0,1},{1,0},{0,2},{2,0}},
{{-35,19},{40,19},{27,-20},{35,-3},{44,20},{22,-21},{35,33},{-19,42},{11,47},{11,37}},
};
double[] answers = {
2.0,
1799.0,
};
for (int i = 0; i < inputs.length; i++) {
System.out.println (Printer.separator ());
int[][] points = inputs[i];
double ans = answers[i], output = tester.largestTriangleArea (points);
System.out.printf ("%s\n%s, expected: %f\n",
Arrays.deepToString (points), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
https://www.sanfoundry.com/c-program-area-triangle/
C Program to Calculate the Area of a Triangle
This C Program calculates the area of a triangle given it’s three sides. The formula or algorithm used is: Area = sqrt(s(s – a)(s – b)(s – c)), where s = (a + b + c) / 2 or perimeter / 2. and a, b & c are the sides of triangle.
Here is source code of the C program to calculate the area of a triangle. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#include <stdio.h>
#include <math.h>
void main()
{
int s, a, b, c, area;
printf("Enter the values of a, b and c \n");
scanf("%d %d %d", &a, &b, &c);
// compute s
s = (a + b + c) / 2;
area = sqrt(s * (s - a) * (s - b) * (s - c));
printf("Area of a triangle = %d \n", area);
}
$ cc pgm1.c -lm
$ a.out
Enter the values of a, b and c
12 10 8
Area of a triangle = 39
上面这个没有用浮点数, 有点问题:
这个的名字叫做: Heron's formula: sqrt (s(s-a) (s-b) (s-c))
import java.lang.Math;
public class Formula
{
double area; double s;
public double findArea(double sideA, double sideB, double sideC)
{
s = 1/2 * (sideA + sideB + sideC);
area = Math.sqrt(s*(s-sideA)*(s-sideB)*(s-sideC));
System.out.println("The area of the triangle is " + area);
return area;
}
}
他这里s处理也不对; 他这个1/2自动变成0了, 这个改一下就行了;
后来看了一下比赛的大部分解法, 好像都没有搞得这么复杂的样子;
2018-05-01 19:55:23 回头来看看我自己这个算法还是挺蠢的; 各种穷搜; 另外这个海伦公式不能上来就随便乱用, 要先判断三角形.
editorial
Approach #1: Brute Force [Accepted]
Intuition
For each possible triangle, check it's area and keep the area of the largest.
Algorithm
We will have 3 for loops to cycle through each choice of 3 points in the array.
After, we'll need a function to calculate the area given 3 points. Here we have some options:
- We can use the Shoelace formula directly, which tells us the area given the 3 points;
- We can use Heron's formula, which requires the 3 side lengths which we can get by taking the distance of two points;
- We can use the formula area = 0.5 a b * sin(C) and calculate the angle C with trigonometry.
总结的还是挺全面的. 头两个选项比较重要, 一个是给你向量(坐标)形式的条件, 一个是给你边长的时候就好用; 如果临场记不清公式, 可以用直角三角形来验证; 然后这两个公式的名字最好熟悉一下;
算角度的话, 估计不太可能会去考;
Our implementation illustrates the use of the shoelace formula.
If we did not know the shoelace formula, we could derive it for triangles with the following approach: starting with points (px, py), (qx, qy), (rx, ry), the area of this triangle is the same under a translation by (-rx, -ry), so that the points become (px-rx, py-ry), (qx-rx, qy-ry), (0, 0).
这个解释就有点扯皮了; 关键还是记忆向量形式; 而不是去死记硬背这个公式; 不过这个可能是awice自己记忆这个公式的方法;
From there, we could draw a square around the triangle with sides touching the coordinate axes, and calculate the area of the square minus the area of the right triangles surrounding the inner triangle.
哦, 他这个记忆方法有点意思啊; 你看我下面解释cchao解法的时候那个图, 还真的是这样, 这样用一个直角坐标系把一个三角形瓜分, 然后分别计算, 就很简单了; 这么说awice这个记忆方法还是挺有意思的;
不过这题最大的收获还是学到了uwi的多边形计算方法;
For more on this approach, see the Wikipedia entry for the Shoelace formula.
class Solution {
public double largestTriangleArea(int[][] points) {
int N = points.length;
double ans = 0;
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
for (int k = j+1; k < N; ++k)
ans = Math.max(ans, area(points[i], points[j], points[k]));
return ans;
}
public double area(int[] P, int[] Q, int[] R) {
return 0.5 * Math.abs(P[0]*Q[1] + Q[0]*R[1] + R[0]*P[1]
-P[1]*Q[0] - Q[1]*R[0] - R[1]*P[0]);
}
}
时间复杂度是N^3, 这个应该是不难理解的; 每一个三角形本身的计算倒是都很简单;
UNFINISHED
contest:
uwi:
class Solution {
public double largestTriangleArea(int[][] points) {
int n = points.length;
double max = 0;
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
for(int k = j+1;k < n;k++){
max = Math.max(max, areaPoly2(points[i], points[j], points[k]));
}
}
}
return max/2;
}
public long areaPoly2(int[]... co)
{
int n = co.length;
long s = 0;
for(int i = 0, j = 1;i < n;i++,j++){
if(j == n)j = 0;
s += (long)co[i][0]*co[j][1]-(long)co[j][0]*co[i][1];
}
return Math.abs(s);
}
}
还没有仔细看, 不过看起来有点像之前看过的一个好像是对一个convext poly求内切三角形的线性算法? 不一定是, 先不要乱想;
2018-05-01 19:58:16 看了一下, 他这个好像对应的是下面多边形的公式? 所以这个影噶就是他的代码库, 他这里实际上你假设先用三角形来理解, 他这个完成的不就是一个xa yb - xb ya这种操作吗;
但是没有算绝对值, 感觉好像有点自己的门道; 而且最后故意返回的实际上是两倍面积(主函数最后有一个/2);
i, j的关系不复杂, 就是(p0 and p1) ... (p(n-1) ... p0)的循环而已; 这种有两个变量的for不要害怕, 一般有一个是主变量, 看清楚这个变量就行了: 他一般是控制范围, 然后另外一个变量, 比如这里的j, 实际上就是一个配合变量而已;
对这个应该是一个多边形面积的算法, 下面那个解释有说: 多边形最后实际上还是拆分成三角形...不对, 他这里不是拆分啊; 你考虑四边形的情况; 他就是告诉你, 这个算法的累加最后返回的是一个两倍面积; 比如给你这个四边形:
他最后的意思就是, 我把ABC, BCD, CDA, DAB全都加起来, 那么最后得到的这个就是一个四边形的两倍面积; 这个有办法证明吗?
cchao下面这个解法还是挺好看懂的; 但是uwi这个感觉有门道啊;
不对, 我懂了, 他这个其实就是一个四边形拆分成三角形; 你看他i和j分别是两个向量, 你可能感觉, 诶, 怎么跟cchao那个做法不一样呢, 那里是挑出来三个点, 然后制作两个向量, 这里直接拿两个点就可以当成向量来用了吗? 但是实际上两个点, implicit的就是代表两个由这两个点和原点形成的两个向量; 看下面两种画法. 按理来说, O在四边形外面还是里面, 应该是没有区别的, 数学处理上面来说;
那么最后我们就按照紫色的来理解, 这个就是一个拆分思路; 四个三角形全都加一遍之后, 其实加的是四个平行四边形的面积, 然后最后/2就行了;
最后一个疑问, 为什么这里可以不用绝对值; 不用绝对值的两个向量的外积, 代表的是什么?
感觉是什么数学上的东西?
TODO: 不懂这个;
cchao:
class Solution {
public:
double largestTriangleArea(vector<vector<int>>& p) {
double ans = 0;
for (auto &x : p) for (auto &y : p) for (auto &z : p) {
int x1 = y[0] - x[0];
int y1 = y[1] - x[1];
int x2 = z[0] - x[0];
int y2 = z[1] - x[1];
double a = fabs(x1 * y2 - y1 * x2) / 2.0;
// printf("%d %d %d %d %f\n", x1, y1, x2, y2, a);
ans = max(ans, a);
}
return ans;
}
};
这个是什么操作?
这个帖子有具体的讲法: https://www.cnblogs.com/xiexinxinlove/p/3708147.html. 这个保存在这里
比较重要的是貌似这个做法还可以拓展到广义的多边形计算上面;
上面这个三阶行列式的计算:
每一项的系数是(-1)^(i+j), 这个我没有记错; 0based还是1based无所谓;
然后cchao这个算法还是好冻的, (x1, y1) and (x2, y2)就是这里参与围成三角形的两个向量;
Problem Description
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.
Difficulty:Easy
Total Accepted:968
Total Submissions:2.1K
Contributor:awice
Companies
google
Related Topics
math