传送门

对于给定的点，先求出凸包，听说水平序求凸包会被卡..亲测不会

然后对于求出来的凸包，求出每一个对踵点。然后对于每一个对踵点，遍历凸包上每一个点，求出最大的叉积和最小的叉积，绝对值的累加即位最大面积。

//BZOJ1069//by Cydiater//2017.1.29#include <iostream>#include <queue>#include <map>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <ctime>#include <iomanip>#include <algorithm>#include <cstdio>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define db 		double#define Vector 		Pointconst int MAXN=1e4+5;const int oo=0x3f3f3f3f;const db eps=1e-10;struct Point{	db x,y;	Point(db x=0,db y=0):x(x),y(y){}};Vector operator + (Point x,Point y){return Vector(x.x+y.x,x.y+y.y);}Vector operator - (Point x,Point y){return Vector(x.x-y.x,x.y-y.y);}Vector operator * (Vector x,db p){return Vector(x.x*p,x.y*p);}Vector operator / (Vector x,db p){return Vector(x.x/p,x.y/p);}int dcmp(db x){if(fabs(x)<eps)return 0;else return x<0?-1:1;}bool operator < (const Vector &x,const Vector &y){return dcmp(x.x-y.x)==0?x.y<y.y:x.x<y.x;}bool operator == (const Vector &x,const Vector &y){return dcmp(x.x-y.x)==0&&dcmp(x.y-y.y)==0;}int N,top=0;Point V[MAXN],q[MAXN];db ans=0;namespace solution{	Point Write(){db x,y;scanf("%lf%lf",&x,&y);return Point(x,y);}	db Cross(Vector x,Vector y){return x.x*y.y-x.y*y.x;}	void Prepare(){		scanf("%d",&N);		up(i,1,N)V[i]=Write();		sort(V+1,V+N+1);		N=unique(V+1,V+N+1)-(V+1);	}	void Andrew(){		up(i,1,N){			while(top>=2&&dcmp(Cross(q[top]-q[top-1],V[i]-q[top-1]))<=0)top--;			q[++top]=V[i];		}		int lim=top;		down(i,N-1,1){			while(top-lim>=1&&dcmp(Cross(q[top]-q[top-1],V[i]-q[top-1]))<=0)top--;			q[++top]=V[i];		}	}	db Area(Point A,Point B){		db area1=0,area2=0;		up(i,1,top){			cmax(area1,Cross(A-q[i],B-q[i])/2);			cmin(area2,Cross(A-q[i],B-q[i])/2);		}		return area1-area2;	}	void Solve(){		Andrew();		top--;		int pos=2;		up(i,1,top){			while(fabs(Cross(q[pos+1]-q[i+1],q[i]-q[i+1]))>fabs(Cross(q[pos]-q[i+1],q[i]-q[i+1]))){				pos%=top;pos++;			}			cmax(ans,Area(q[pos],q[i]));		}		printf("%.3lf\n",ans);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

BZOJ1069: [SCOI2007]最大土地面积