http://poj.org/problem?id=2079
题目大意：求最大面积的三角形。
——————————————————
可以知道，最大面积的三角形的顶点一定是最大凸包的顶点。
接下来就是O(n*n)的常数优化题了（利用单峰性）。
（但其实不是n*n的，因为我们求的是纯凸包，所以n会小一些）
#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
const dl eps=1e-;
const int N=;
struct point{
dl x;
dl y;
}p[N],q[N];
int n,per[N],l;
inline point getmag(point a,point b){
point s;
s.x=b.x-a.x;s.y=b.y-a.y;
return s;
}
inline dl multiX(point a,point b){
return a.x*b.y-b.x*a.y;
}
inline dl dis(point a,point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline bool cmp(int u,int v){
dl det=multiX(getmag(p[],p[u]),getmag(p[],p[v]));
if(fabs(det)>eps)return det>eps;
return dis(p[],p[u])-dis(p[],p[v])<-eps;
}
void graham(){
int id=;
for(int i=;i<=n;i++){
if(p[i].x-p[id].x<-eps||(fabs(p[i].x-p[id].x)<eps&&p[i].y-p[id].y<-eps))id=i;
}
if(id!=)swap(p[],p[id]);
for(int i=;i<=n;i++)per[i]=i;
sort(per+,per+n+,cmp);
l=;
q[++l]=p[];
for(int i=;i<=n;i++){
int j=per[i];
while(l>=&&multiX(getmag(q[l-],p[j]),getmag(q[l-],q[l]))>-eps){
l--;
}
q[++l]=p[j];
}
return;
}
inline dl area(){
if(l<=)return ;
dl ans=;
for(int i=;i<=l;i++){
int j=i%l+;
int k=j%l+;
while(){
dl s1=multiX(getmag(q[i],q[j]),getmag(q[i],q[k]));
dl s2=multiX(getmag(q[i],q[j]),getmag(q[i],q[k%l+]));
if(fabs(s1)-fabs(s2)>-eps){
break;
}
k=k%l+;
}
while(i!=j&&j!=k&&i!=k){
dl s=multiX(getmag(q[i],q[j]),getmag(q[i],q[k]));
ans=max(ans,fabs(s)/2.0);
while(){
dl s1=multiX(getmag(q[i],q[j]),getmag(q[i],q[k]));
dl s2=multiX(getmag(q[i],q[j]),getmag(q[i],q[k%l+]));
if(fabs(s1)-fabs(s2)>-eps){
break;
}
k=k%l+;
}
j=j%l+;
}
}
return ans;
}
int main(){
while(scanf("%d",&n)!=EOF&&n!=-){
for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
graham();
printf("%.2f\n",area());
}
return ;
}