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