Eva

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4753  Solved: 1932
Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output 

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT 

数据范围 n<=2000, |x|,|y|<=100000

/**************************************************************

    Problem: 1069

    User: ictsing

    Language: C++

    Result: Accepted

    Time:272 ms

    Memory:1388 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int mt=2000+5;

struct vec{

   double x,y;

}ovo[mt],qaq[mt<<1];

double ans=0;

int top=0,n;

vec operator - (vec a,vec b)

{

    vec t;

    t.x=a.x-b.x,t.y=a.y-b.y;

    return t;

}

double operator * (vec a,vec b)

{

    return a.x*b.y-a.y*b.x;

}

double dis(vec a,vec b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

bool cmp(vec a,vec b)

{

    double t=(a-ovo[1])*(b-ovo[1]);

    if(t==0) return dis(a,ovo[1])<dis(b,ovo[1]);

    return t>0;

}

void graham()

{

    int tmp=1;

    for(int i=2;i<=n;i++)

       if(ovo[tmp].y>ovo[i].y||(ovo[tmp].x>ovo[i].x&&ovo[tmp].y==ovo[i].y)) tmp=i;

    swap(ovo[1],ovo[tmp]);

    sort(ovo+2,ovo+n+1,cmp);

    top=0;

    qaq[++top]=ovo[1],qaq[++top]=ovo[2];

    for(int i=3;i<=n;i++)

    {

        while((qaq[top]-qaq[top-1])*(ovo[i]-qaq[top-1])<=0) top--;

        qaq[++top]=ovo[i];

    }

}

void rotcalip()

{

    for(int i=1;i<=top;i++) qaq[top+i]=qaq[i];

    for(int i=1;i<=top;i++)

    {

        int l=i+1,r=i+3;

        for(int j=i+2;j<=n;j++)

        {

           while(l+1<j&&(qaq[l+1]-qaq[i])*(qaq[j]-qaq[i])>(qaq[l]-qaq[i])*(qaq[j]-qaq[i])) l++;

           while(r+1-top<i&&(qaq[j]-qaq[i])*(qaq[r+1]-qaq[i])>(qaq[j]-qaq[i])*(qaq[r]-qaq[i])) r++;//乘法顺序很重要

           ans=max(ans,(qaq[l]-qaq[i])*(qaq[j]-qaq[i])+(qaq[j]-qaq[i])*(qaq[r]-qaq[i]));

        }

    }

    ans/=2.0;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%lf%lf",&ovo[i].x,&ovo[i].y);

    graham();

    rotcalip();

    printf("%.3lf\n",ans);

    return 0;

}

/*

5

0 0

1 0

1 1

0 1

0.5 0.5

*/