nyoj 952 最大四边形

描述
平面坐标上有n个点，你知道能组成四边形中面积最大的是多少吗？
输入
有多组测试数据
第一行整数n，表示有n个点，( 4<=n<=300 )
然后n行，每行x，y表示点的坐标。(没有重复的点)
输出
最大四边形的面积.(保留六位小数)
样例输入
5
0 0
0 4
4 0
4 4
2 3
样例输出

16.000000

思路：

以O(n2)枚举每一条边，以这条边作为四边形的对角线（注意：这里所说的 对角线是指把四边形分成两部分的线，不考虑凹四边形可能出现的两个点在对角线同一侧的情况），以O(n)枚举每一个点，判断是在对角线所在直线的左侧还是 右侧。因为被对角线分割开的两三角形不相关，所以可以单独讨论：分别找出左右两侧的最大三角形，二者之和即为此边对应的最大四边形。整个算法为 O(n3)。

求三角形的面积：叉乘公式

A(x1,y1)    B(x2,y2)      C(x3,y3)

s=((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/2

如果s<0,表示A,B,C三点顺时针，反之。

#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
#define eps 1e-10

#define maxn 310
struct point
{
    double x,y;
}Point[maxn];


double cross(point p1,point p2,point p0)///叉乘求三角形的面积
{
    return ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x))*0.5;
}

double max(double a,double b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%lf %lf",&Point[i].x,&Point[i].y);
        double ans=0,lmax=0,rmax;
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)///这两个for是枚举对角线的两个点
            {
                rmax=0,lmax=0;
                for(int k=0; k<n; k++)///这是枚举对角线两侧的点
                {
                    if(k!=i && k!=j)
                    {
                        double s=cross(Point[i],Point[j],Point[k]);
                        /*利用叉乘求三角形面积，点的顺时针，
                        逆时针的正负不同，知道这个点在对角线的哪侧，
                        分别求出各侧面积的最大的，俩个相加，就为这条对角线所获的最大四边形面积*/
                        if(s<eps)
                        {
                            lmax=max(lmax,-s);
                        }
                        else
                        {
                            rmax=max(rmax,s);
                        }
                    }
                }
                if(lmax==0 || rmax==0)continue;///判断是否构成四边形
                ans=max(ans,(rmax+lmax));///比较各对角线所获的最大四边形的面积
            }
        }
        printf("%.6lf\n",ans);
    }
    return 0;
}