将四边形拆成两个三角形。旋转卡壳经典题。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef int lint;
const int maxn = 2001;
const double eps = 1e-12;
const double PI = acos(-1.0);
int sgn(double x)
{if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1;
}
struct Point
{double x,y;Point(){}Point(double _x,double _y){ x = _x;y = _y;}Point operator -(const Point &b)const{return Point(x - b.x,y - b.y);}
//叉积double operator ^(const Point &b)const{return x*b.y - y*b.x; }
//点积double operator *(const Point &b)const{return x*b.x + y*b.y; }
//绕原点旋转角度B（弧度值），后x,y的变化void transXY(double B){double tx = x,ty = y; x = tx*cos(B) - ty*sin(B);y = tx*sin(B) + ty*cos(B);}
};
struct Line
{Point s,e;Line(){}Line(Point _s,Point _e){ s = _s;e = _e;}pair<int,Point> operator &(const Line &b)const{Point res = s;if(sgn((s-e)^(b.s-b.e)) == 0){if(sgn((s-b.e)^(b.s-b.e)) == 0)return make_pair(0,res);//重合else return make_pair(1,res);//平行}double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));res.x += (e.x-s.x)*t;res.y += (e.y-s.y)*t;return make_pair(2,res);}
};
Point PointToLine(Point P,Line L)
{Point result;double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));result.x = L.s.x + (L.e.x-L.s.x)*t;result.y = L.s.y + (L.e.y-L.s.y)*t;return result;
}
double dist(Point a,Point b)
{return sqrt((a-b)*(a-b));
}
int dist2(Point a,Point b)
{return (a-b)*(a-b);
}
Point lis[maxn];
int Stack[maxn],top;
//相对于list[0]的极角排序bool _cmp(Point p1,Point p2)
{double tmp = (p1-lis[0])^(p2-lis[0]);if(sgn(tmp) > 0)return true;else if(sgn(tmp) == 0 && sgn(dist(p1,lis[0]) - dist(p2,lis[0])) <= 0)return true;else return false;
}
void Graham(int n)
{Point p0;int k = 0;p0 = lis[0];
//找最下边的一个点for(int i = 1;i < n;i++){if( (p0.y > lis[i].y) || (p0.y == lis[i].y && p0.x > lis[i].x) ){p0 = lis[i];k = i;}}swap(lis[k],lis[0]);sort(lis+1,lis+n,_cmp);if(n == 1){top = 1;Stack[0] = 0;return; }if(n == 2){top = 2;Stack[0] = 0;Stack[1] = 1;return ; }Stack[0] = 0;Stack[1] = 1;top = 2;for(int i = 2;i < n;i++){while(top > 1 &&sgn((lis[Stack[top-1]]-lis[Stack[top-2]])^(lis[i]-lis[Stack[top-2]])) <=0)top--;Stack[top++] = i;}
}
lint ans1[maxn][maxn],ans2[maxn][maxn],flag1[maxn][maxn],flag2[maxn][maxn];
void rotating_calipers(Point p[],int n)
{Point v;for( int i = 0;i < n;i++ ){lint cur = (i+2)%n;lint cur2 = i;for( int j = i+2; j < n ;j++ ){if( i == 0 && j == n-1 ) break;while( ((p[i] - p[j])^( p[(cur+1)%n] - p[cur] )) < 0 ) cur = (cur+1)%n;while( ((p[i] - p[j])^( p[(cur2+1)%n]-p[cur2] )) > 0 ) cur2 = (cur2+1)%n;ans1[i][j] = cur;flag1[i][j] = 1;ans2[i][j] = cur2;flag2[i][j] = 1;}}return;
}
Point p[maxn];
int main(){lint n;double x,y;lint tot = 0;scanf("%d",&n);for( lint i = 1;i <= n;i++ ){scanf("%lf%lf",&x,&y);lis[tot++] = Point( x,y );}Graham(n);for( lint i = 0;i < top;i++ ){p[i] = lis[Stack[i]];}rotating_calipers( p,top );double ans  = 0;for( lint i = 0;i < top;i++ ){for( lint j = 0;j < top;j++ ){if( flag1[i][j]&&flag2[i][j] ){Point x = p[i] - p[j];Point y1 = p[ans1[i][j]] - p[j];Point y2= p[ ans2[i][j] ] - p[j];ans = max( ans,(abs((x^y1)) + abs((x^y2)))/2 );}}}printf("%.3lf\n",ans);return 0;
}

 水平排序版本

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef int lint;
const int maxn = 2001;
const double eps = 1e-12;
const double PI = acos(-1.0);
int sgn(double x)
{if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1;
}
struct Point
{double x,y;Point(){}Point(double _x,double _y){ x = _x;y = _y;}Point operator -(const Point &b)const{return Point(x - b.x,y - b.y);}
//叉积double operator ^(const Point &b)const{return x*b.y - y*b.x; }
//点积double operator *(const Point &b)const{return x*b.x + y*b.y; }
//绕原点旋转角度B（弧度值），后x,y的变化void transXY(double B){double tx = x,ty = y; x = tx*cos(B) - ty*sin(B);y = tx*sin(B) + ty*cos(B);}
};
struct Line
{Point s,e;Line(){}Line(Point _s,Point _e){ s = _s;e = _e;}pair<int,Point> operator &(const Line &b)const{Point res = s;if(sgn((s-e)^(b.s-b.e)) == 0){if(sgn((s-b.e)^(b.s-b.e)) == 0)return make_pair(0,res);//重合else return make_pair(1,res);//平行}double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));res.x += (e.x-s.x)*t;res.y += (e.y-s.y)*t;return make_pair(2,res);}
};
Point PointToLine(Point P,Line L)
{Point result;double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));result.x = L.s.x + (L.e.x-L.s.x)*t;result.y = L.s.y + (L.e.y-L.s.y)*t;return result;
}
double dist(Point a,Point b)
{return sqrt((a-b)*(a-b));
}
int dist2(Point a,Point b)
{return (a-b)*(a-b);
}
Point lis[maxn];
int Stack[maxn],top;
//相对于list[0]的极角排序bool _cmp(Point p1,Point p2)
{if( !sgn( p1.x-p2.x ) ) return p1.y < p2.y;return p1.x < p2.x;
}
void Graham(int n)
{sort(lis,lis+n,_cmp);top = 0;for(int i = 0;i < n;i++){while(top > 1 &&sgn((lis[Stack[top-1]]-lis[Stack[top-2]])^(lis[i]-lis[Stack[top-2]])) <=0)top--;Stack[top++] = i;}int k = top;for( int i = n-2;i >= 0;i-- ){while( top > k && sgn((lis[Stack[top-1]]-lis[Stack[top-2]])^(lis[i]-lis[Stack[top-2]])) <=0 ){top--;}Stack[ top++ ] = i;}top--;
}
lint ans1[maxn][maxn],ans2[maxn][maxn],flag1[maxn][maxn],flag2[maxn][maxn];
void rotating_calipers(Point p[],int n)
{Point v;for( int i = 0;i < n;i++ ){lint cur = (i+2)%n;lint cur2 = i;for( int j = i+2; j < n ;j++ ){if( i == 0 && j == n-1 ) break;while( ((p[i] - p[j])^( p[(cur+1)%n] - p[cur] )) < 0 ) cur = (cur+1)%n;while( ((p[i] - p[j])^( p[(cur2+1)%n]-p[cur2] )) > 0 ) cur2 = (cur2+1)%n;ans1[i][j] = cur;flag1[i][j] = 1;ans2[i][j] = cur2;flag2[i][j] = 1;}}return;
}
Point p[maxn];
int main(){lint n;double x,y;lint tot = 0;scanf("%d",&n);for( lint i = 1;i <= n;i++ ){scanf("%lf%lf",&x,&y);lis[tot++] = Point( x,y );}Graham(n);for( lint i = 0;i < top;i++ ){p[i] = lis[Stack[i]];}rotating_calipers( p,top );double ans  = 0;for( lint i = 0;i < top;i++ ){for( lint j = 0;j < top;j++ ){if( flag1[i][j]&&flag2[i][j] ){Point x = p[i] - p[j];Point y1 = p[ans1[i][j]] - p[j];Point y2= p[ ans2[i][j] ] - p[j];ans = max( ans,(abs((x^y1)) + abs((x^y2)))/2 );}}}printf("%.3lf\n",ans);return 0;
}