Steven_MengのBlog

传送门

$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);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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);
}

 评论