nyoj 最大四边形 952 （数学几何+技巧） 好题

最大四边形

时间限制： 1000 ms  |           内存限制： 65535 KB 难度： 2

描述

平面坐标上有n个点，你知道能组成四边形中面积最大的是多少吗？

输入

有多组测试数据

第一行整数n，表示有n个点，( 4<=n<=300 )

然后n行，每行x，y表示点的坐标。(没有重复的点)

输出

最大四边形的面积.(保留六位小数)

样例输入

5
0 0
0 4
4 0
4 4
2 3      

样例输出

16.000000      

/*用一种简单方法，就是用两层循环枚举四边形的对称轴，再用一层循环枚举一个点，
判断这个点四边形的左边还是右边，分别算出这个对称轴左半部分和右半部分最大
的面积。相加就是最大的，注意左半部分和右半部分的面积不能是0，排除是三角形的情况*/
#include<stdio.h>
#include<string.h>
struct zz
{
	double x;
	double y;
}p[310];
double max(double a,double b)
{
	return a>b?a:b;
}
double judge(zz a,zz b,zz c)
{
	return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))*0.5;//三角形面积 
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		double ans=0,r=0,l=0,s;
		int i,j,k;
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				r=l=0;
				for(k=0;k<n;k++)
				{
					if(k!=i&&k!=j)
					{
						s=judge(p[i],p[j],p[k]);
						if(s<0)
							l=max(l,-s);
						else
							r=max(r,s);
					}
				}
				if(l!=0&&r!=0)
					ans=max(ans,l+r);
			}
		}
		printf("%.6lf\n",ans);
	}
	return 0;
}