Poj Solution 2079

http://poj.org/problem?id=2079

#include<iostream>
#include"stdio.h"
#include<algorithm>
//ifstream in("triangle.in");
//#define cin in

using namespace std;

/////////////////////////
#define Type long /*�������*/
/////////////////////////


struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}




const double pi=3.14159265359;

inline Type cheng(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}




//n*log(n)
//��͹��,����͹���ϵĵ�ĸ���wall:͹�������

//p�����������!!!

int convex(point *p,int n,point *wall)
{int i;int st;Type h;
int stack[50011],sign[50011];

st=0;
stack[st++]=0;
stack[st++]=1;

for(i=0;i<n;i++)sign[i]=0;

sign[1]=1;
i=2;

while(i<n)
{while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ >= /**/ 0)
//��͹�����Ҳ�㣬use '>'
{st--;if(h)sign[stack[st]]=0;}
stack[st++]=i;sign[i]=1;i++;
}

i--;

while(i>=0)
{while(sign[i])i--;

while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ >= /**/ 0)st--;

stack[st++]=i;
i--;
}

st--;

if(wall){for(i=0;i<st;i++)wall[i]=p[stack[i]];}

return st;
}


point wall[50010];
point p[50010];
long n,s;

inline long ab(long a)
{
    return a>0?a:-a;
}

int main()
{
    long i,j,l;long k,h;
    while(1)
    {
        //cin>>n;
        scanf("%ld",&n);
        if(n<0)break;

        for(i=0;i<n;i++)
        {
            //cin>>p[i].x>>p[i].y;
            scanf("%ld%ld",&p[i].x,&p[i].y);
        }

        sort(p,n);
        if(n>3)n=convex(p,n,wall);
        else for(i=0;i<n;i++)wall[i]=p[i];

        s=cheng(wall[0],wall[1],wall[2]);
        s=s>0?s:-s;
        
        for(l=1,i=3;i<n;i++)
        {
            k=0;
            for(j=l;j<i;j++)
            {
                h=ab(cheng(wall[i],wall[j],wall[k]) );
                while(k<j-1&&(h=ab(cheng(wall[i],wall[j],wall[k]) ))<ab(cheng(wall[i],wall[j],wall[k+1])) )
                    k++;
                if(h>s)
                {
                    s=h;
                    l=j;
                }
            }
        }


        printf("%.2lfn",(double)s/2);
    }
    return 0;
}