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;
}