  fzu 1302
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-8
using namespace std;
struct pt
{
double x,y;
}p1[50010],p2[50010];
int dblcmp(double x)
{
if(fabs(x)<eps)
return 0;
return x<0?-1:1;
}
double cross(pt a,pt b,pt c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dist(pt a,pt b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(pt a,pt b)
{
int t=dblcmp(cross(p1[0],a,b));
if(t==0)
return dist(p1[0],a)<dist(p1[0],b);
else return t>0;
}
int n;
int Tubao()
{
int swap=0;
int i;
for(i=1;i<n;i++)
if(p1[i].y<p1[swap].y||(p1[i].y==p1[swap].y&&p1[i].x<p1[swap].x))
swap=i;
p2[0]=p1[0];
p1[0]=p1[swap];
p1[swap]=p2[0];
sort(p1+1,p1+n,cmp);
p2[0]=p1[0];
p2[1]=p1[1];
int top=1;
for(i=2;i<n;i++)
{
while(top>0&&dblcmp(cross(p2[top-1],p2[top],p1[i]))<=0)
top--;
p2[++top]=p1[i];
}
return top+1;
}
int main()
{
int i,j,k;
while(scanf("%d",&n)!=EOF)
{
if(n==-1)
break;
for(i=0;i<n;i++)
{
scanf("%lf%lf",&p1[i].x,&p1[i].y);
}
if(n <= 2){
printf("0.00\n");
continue;
}
if(n == 3){
printf("%.2lf\n", fabs(cross(p1[0], p1[1], p1[2]))/2);
continue;
}
n=Tubao();
double best=-1;
double area2;
for(i=0;i<=n-3;i++)//O(n^2)利用峰值原理，以某條邊為底邊枚舉點旋轉有一個最大面積峰值。到峰值后旋轉底邊，再繼續旋轉點，到峰值再旋轉……
{
k=0;
for(j=i+1;j<=n-2;j++)
{
if(k<=j)
k=j+1;
area2=fabs(cross(p2[i],p2[j],p2[k]));
if(area2>best)
best=area2;
while(k+1<=n-1)
{
double tmp=fabs(cross(p2[i],p2[j],p2[k+1]));
if(tmp<area2)
break;
best=max(best,tmp);
area2=tmp;
k++;
}
}
}
printf("%.2f\n",best/2);
}
}
|