欢迎参加程序设计竞赛~
程序设计竞赛中有着很多有意思的问题,其中,与三角形有关的问题就经常出现。今天你要解决的,就是其中最简单的一个问题:
给定平面直角坐标系上的N个点,保证这N个点中任意三点都不共线。求任意三点能够构成的三角形中,面积最大的三角形的面积。
输入
输入的第一行是一个整数T(1 <= T <= 10),表示一共有T组用例。
每组用例的第一行为一个整数N(3 <= n <= 100),表示平面上点的个数。接下来的N行,每行包含两个用空格隔开的整数Xi和Yi(-1000 <= Xi, Yi <= 1000),表示第i个点的坐标(Xi, Yi)。
输出
每组用例输出一个数,表示最大的三角形的面积,结果保留一位小数。
输入样例
2
4
-1 1
1 1
1 -1
-1 -1
3
-1 -1
3 0
0 0
输出样例
2.0
1.5
#include <stdio.h>
#include<math.h>
int main()
{
int T,N,m,n,k;
int a[100],b[100];
float x,y,z,p,s,smax=0;
int i,j;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%d",&N);
for(j=1;j<=N;j++){
scanf("%d %d",&a[j-1],&b[j-1]);
}
// for(j=1;j<=N;j++){
// printf("%d %d\n",a[j-1],b[j-1]);
// }
for(m=0;m<=N-3;m++)
for(n=m+1;n<=N-2;n++)
for(k=n+1;k<=N-1;k++){
x=sqrt(((float)a[m]-(float)a[n])*((float)a[m]-(float)a[n])+((float)b[m]-(float)b[n])*((float)b[m]-(float)b[n]));
y=sqrt(((float)a[n]-(float)a[k])*((float)a[n]-(float)a[k])+((float)b[n]-(float)b[k])*((float)b[n]-(float)b[k]));
x=sqrt(((float)a[k]-(float)a[m])*((float)a[k]-(float)a[m])+((float)b[k]-(float)b[m])*((float)b[k]-(float)b[m]));
p=(x+y+z)/2;
s=sqrt(p*(p-x)*(p-y)*(p-z));
if(s>smax) smax=s;
}
printf("%.1f",smax);
smax=0;
}
return 0;
}