P4166 [SCOI2007]最大土地面积

$Pro$

在某块平面土地上有 $N$ 个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。

$Sol$

考虑把四边形分成两个三角形，显然这个四边形的四个顶点都在凸包上面，于是考虑枚举四边形的两个端点 $i$ ， $j$ ，然后另外两个端点 $a$ ， $b$ 可以通过单调性求出。

如图：

考虑按照顺时针（图中的正方向）枚举端点 $i$ ， $j$ ，当 $j$ 移动到下一个位置 $j'$ 的时候，考虑 $a$ ， $b$ 的移动，发现 $a$ ， $b$ 都是沿着正方向移动，于是单调地移动 $a$ ， $b$ ，直到面积不增加才停止。

1
2

while (Next(a)!=j&&Area(stk[Next(a)]-stk[i],stk[Next(a)]-stk[j])>Area(stk[a]-stk[i],stk[a]-stk[j])) a=Next(a);
while (Next(b)!=i&&Area(stk[Next(b)]-stk[i],stk[Next(b)]-stk[j])>Area(stk[b]-stk[i],stk[b]-stk[j])) b=Next(b);

其中 $Area$ 函数算的是两个向量所夹的三角形的面积，直接叉积 $/2$ 后面取绝对值即可。

几何意义可以看下图：

1
2
3

inline double Area(const Point &A,const Point &B){
    return abs(A*B/2.00);
}

注意初始点的选择，图中用绿色箭头标出。

#include <bits/stdc++.h>
#include <cmath>
#define MAXN 2005
#define eps 1e-10
using namespace std;
struct Point{
	double x,y;
}p[MAXN];
Point p0;
int pos;
inline double operator * (const Point &A,const Point &B){
	return A.x*B.y-A.y*B.x;
}
inline Point operator - (const Point &A,const Point &B){
	return Point{A.x-B.x,A.y-B.y};
}
inline Point operator + (const Point &A,const Point &B){
	return Point{A.x+B.x,A.y+B.y};
}
inline double pf(double x){
	return x*x;
}
inline double dis(const Point &A,const Point &B){
	return sqrt(pf(A.x-B.x)+pf(A.y-B.y));
}
inline bool operator < (const Point &A,const Point &B){
	if (abs((A-p0)*(B-p0))>eps) return ((A-p0)*(B-p0))>eps;
	else return dis(p0,A)<dis(p0,B);
}
Point stk[MAXN];
int top,cnt;
inline void Insert(Point a){
	p[++cnt]=a;
	if (p[pos].y>p[cnt].y||(p[pos].y==p[cnt].y&&p[pos].x>p[cnt].x)) pos=cnt;
}
inline int Next(int x){
    return (x>=top?x-top+1:x+1);
}
inline double Area(const Point &A,const Point &B){
    return abs(A*B/2.00);
}
int main(){
	int n;
	scanf("%d",&n);
	pos=1;
	for (register int i=1;i<=n;++i){
		double x,y;
		scanf("%lf%lf",&x,&y);
		Insert(Point{x,y});
	}
	p0=p[pos];
	swap(p[1],p[pos]);
	sort(p+2,p+1+cnt);
	for (register int i=1;i<=cnt;++i){
		while (top>1&&(stk[top]-stk[top-1])*(p[i]-stk[top-1])<=0) top--;
		stk[++top]=p[i];
	}
    double ans=0;
    for (register int i=1;i<=top;++i){//枚举凸包第一个端点
        int a=Next(i),b=Next(Next(Next(i)));
        for (register int j=Next(Next(i));j<=top;j++){//枚举第一个端点的对角线端点
            while (Next(a)^j&&Area(stk[Next(a)]-stk[i],stk[Next(a)]-stk[j])>Area(stk[a]-stk[i],stk[a]-stk[j])) a=Next(a);
            while (Next(b)^i&&Area(stk[Next(b)]-stk[i],stk[Next(b)]-stk[j])>Area(stk[b]-stk[i],stk[b]-stk[j])) b=Next(b);
            ans=max(ans,Area(stk[a]-stk[i],stk[a]-stk[j])+Area(stk[b]-stk[i],stk[b]-stk[j]));
        }
    }
	printf("%.3f\n",ans);
}