出构成的最大的三角形的面积，结果保留两位小数。C语言，谢谢

问题描述：

Problem Description
老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。

Input
输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.

Output
对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。

Sample Input
3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7

Sample Output
1.50
27.00

答

https://blog.csdn.net/wenbo201/article/details/76070678

答

//a(a,b) b(c,d) c(e,f)
//（ab+be+cf-ed-af-bc)的绝对值除以2
float s = 0;
float temp=0;
for(int i=0;i<pointCount-1;;i++)
for(int j=2;j<pointCount;j++)
{
temp = fabs(point[i].x*point[i].y+point[i].y+point[j].y+point[i+1].x*point[j].y-point[i].x*point[i+1].y-point[i].x*point[j].y-point[i].y*point[i+1].x)/2;
if(temp<s)
s = temp;
}

答

任意三个点构成的最大的三角形的面积

#include
#include
#define MAX 100
int b[2][MAX], a[MAX], x, y, z, c[MAX], d[3][MAX];
double Area[MAX];
double area(double a, double b, double c)
{
double p = (a + b + c) / 2;
return sqrt(p*(p - a)*(p - b)*(p - c));
}

void comb(int n, int r)
{
int i, j,*p;
p = &c[0];
i = 0;
a[i] = 1;
do
{
if (a[i] - i <= n - r + 1)

{

        if (i == r - 1)             
        {

            for (j = 0; j < r; j++)
            {

                //printf("%4d", a[j]);
                *p = a[j];
                p++;
            }
            //printf("\n");
            a[i]++;
            continue;
        }
        i++;                    
        a[i] = a[i - 1] + 1;
    }
    else                        
    {
        if (i == 0)             
            return;
        a[--i]++;
    }
} while (1);

}

double cptlen(int x1,int y1,int x2,int y2)
{
double len = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return len;
}
void main()
{
printf("输入一个大于等于3的数:\n");

int num, tem_a, tem_b;
scanf("%d", &num);
//getchar();
for (int i = 0; i < num; i++)
{

    scanf("%d%d", &tem_a,&tem_b);

    getchar();

    b[0][i] = tem_a;
    b[1][i] = tem_b;
}
comb(num, 3);
//for (int j = 0; j < num;j++)
//{
//  printf("%d,%d\n", b[0][j], b[1][j]);
//}
//for (int j = 0; j < sizeof(c)&&c[j]!=0; j++)
//{
//  
//      printf("%d\n", c[j]);
//
//}
double *q;
q = &Area[0];

for (int j = 0; j < sizeof(c) && c[j+2] != 0; j=j+3)
{

    //printf("%d,%d,%d\n", c[j], c[j+1], c[j+2]);
    int x1, y1, x2, y2, x3, y3;
    x1 = b[0][c[j]-1];
    y1 = b[1][c[j]-1];
    x2 = b[0][c[j + 1]-1];
    y2 = b[1][c[j + 1]-1];
    x3 = b[0][c[j + 2]-1];
    y3 = b[1][c[j + 2]-1];

    double a, b, c;

    a = cptlen(x1, y1, x2, y2);
    b = cptlen(x2, y2, x3, y3);
    c = cptlen(x1, y1, x3, y3);


    *q = area(a,b,c);

    q++;

}


double area_max = 0;
for (int i = 0; i < sizeof(Area)&&Area[i]!=0;i++)
{
    if (Area[i]>area_max)
    {
        area_max = Area[i];
    }
}

printf("%0.2f",area_max);

getchar();

}

出构成的最大的三角形的面积，结果保留两位小数。C语言，谢谢

相关推荐