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

This entry was posted in poj. Bookmark the permalink.