分析
显然选的点要在凸包上。于是先求出凸包。
然后，旋转卡壳确定一条对角线，然后$O(n)$扫描，找到对角线左右两个面积最大的三角形，合起来就是四边形的面积。
总时间复杂度$O(n^2)$。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<'9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=2000+10;
const int INF=0x3f3f3f3f;
struct Point { double x,y; };
typedef Point Vector;
Vector operator -(const Point a,const Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
int n,top=0;
Point a[N],s[N];
inline int cmp(Point u,Point v) {
double A=atan2(u.y-a[1].y,u.x-a[1].x);
double B=atan2(v.y-a[1].y,v.x-a[1].x);
if (A!=B) return A<B;
else return u.x<v.x;
}
inline void Graham() {
int pos=1;
for (re int i=2;i<=n;++i)
if (a[i].y<a[pos].y||(a[i].y==a[pos].y&&a[i].x<a[pos].x)) pos=i;
swap(a[1],a[pos]); sort(a+2,a+n+1,cmp);
s[top=1]=a[1];
for (re int i=2;i<=n;++i) {
while (top>1&&cross(s[top]-s[top-1],a[i]-s[top])<=0) --top;
s[++top]=a[i];
}
s[top+1]=s[1];
}
inline double calc(int x,int y) {
double ans=0,tmp=0;
for (re int i=x;i!=y;i=i%top+1)
tmp=max(tmp,fabs(cross(s[i]-s[x],s[i]-s[y])/2));
ans+=tmp,tmp=0;
for (re int i=y;i!=x;i=i%top+1)
tmp=max(tmp,fabs(cross(s[i]-s[x],s[i]-s[y])/2));
ans+=tmp; return ans;
}
inline void Solve() {
double ans=0;
for (re int i=1,j=3;i<=top;++i) {
while (cross(s[j]-s[i],s[i+1]-s[j])>cross(s[j+1]-s[i],s[i+1]-s[j+1])) j=j%top+1;
ans=max(ans,calc(i,j)),ans=max(ans,calc(i%top+1,j));
}
printf("%.3f\n",ans);
}
int main() {
n=read();
for (re int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
Graham();
Solve();
return 0;
}
%%%julao
计算几何聚聚%%%
您早就会了啊...
但还是被您吊打啊