平面有100个点,任意三个点可以构成一个三角形。编一个程序,输入100个点的坐标,输出在构成的所有三角形中,最大的三角形的面积。
代码如下:
#include<stdio.h>
double area(int x1,int y1,int x2,int y2,int x3,int y3)
{
return (x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1)/2;
}
int main()
{
int x[100]={
1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,
1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,
1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,
1,2,3,4,5,6,7,8,9,10
};
int y[100]={
2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,
2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,
2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,2,3,4,5,2,5,6,7,11,88,
2,3,4,5,2,5,6,7,11,88
};
double maxx=0.0;
for(int i=0;i<98;i++)//选第一个节点
{
for(int j=i+1;j<99;j++)//选第二个节点
{
for(int k=j+1;k<100;k++)//选第三个节点
{
double S=area(x[i],y[i],x[j],y[j],x[k],y[k]);
if(S>maxx) maxx=S;
}
}
}
printf("%lf\n",maxx);
return 0;
}
https://www.cnblogs.com/Running-Time/p/4753089.html
方法1:行列式
设三角形的面积为S, 则S = (1/2)*(下面行列式)
|x1 y1 1|
|x2 y2 1|
|x3 y3 1|
即 S=(1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2) = (1 / 2) * ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
代码:
1 2 3 4 |
//行列式计算三角形面积 double area(Point p1, Point p2, Point p3) { return fabs (0.5 * ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))); } |
方法2:海伦公式
S = sqrt (p * (p - a)(p - b)(p - c)) 其中p = (a + b + c) / 2, abc为三角形三边长
代码:
1 2 3 4 5 6 7 8 9 10 11 12 |
double dis(Point p1, Point p2) { return sqrt ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } //海伦公式计算三角形面积 double area(Point p1, Point p2, Point p3) { double a = dis (p1, p2); double b = dis (p2, p3); double c = dis (p3, p1); double p = (a + b + c) * 0.5; return sqrt (p * (p - a) * (p - b) * (p - c)); } |