bzoj1069-最大土地面积

时间:2022-03-30 07:48:26

题目

给定\(n\ (n\le 2000)\)个坐标,求四个坐标使得围起来的四边形面积最大。

分析

最暴力的想法是枚举四个点,然而肯定超时。接着不知道怎么想到中途相遇,然而一点关系都没有。这里用到了一个单调性:

如果在凸包上确定了一个点\(x\),令\(x\)逆时针方向的第一个点为\(y\),这时确定了一个点\(z\)使得\(S_{\triangle XYZ}最大,那么当\)y\(逆时针移动的时候,使得三角形面积最大的点\)z\(就会不动或逆时针移动。这个性质发展成为我们说的旋转卡壳。
这就是说,如果在凸包上确定了一个点,那么我们可以\)O(n)\(求出包含这个点的所有凸包上的四边形的最大面积。
所以我们可以枚举所有点,在\)O(n^2)$中求出答案。

代码

这里有几个地方需要注意到。

  1. 求凸包极角排序的时候,选择的基础点一定是最下面,最左边的,而不可以仅仅是最下面的,否则会出现\(0\)和\(-0\)这种情况。
  2. 在求凸包单调栈弹出的时候,要用小于等于号,否则如果有重点的情况就会出现问题。
  3. 在计算答案时,每次移动\(j\)的时候要记得更新\(s1\)和\(s2\)。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e3+10;
struct node {
double x,y;
} a[maxn],sta[maxn];
int top=0;
double P(double x) {
return x*x;
}
double dis(node a,node b) {
return sqrt(P(a.x-b.x)+P(a.y-b.y));
}
double cross(node a,node b,node c) {
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(node e,node f) {
double tmp=cross(a[1],e,f);
if (tmp>0) return true;
if (tmp<0) return false;
return dis(a[1],e)<dis(a[1],f);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("my.out","w",stdout);
#endif
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i) {
scanf("%lf%lf",&a[i].x,&a[i].y);
if (a[i].y<a[1].y || (a[i].y==a[1].y && a[i].x<a[1].x)) swap(a[1],a[i]); // here
}
sort(a+2,a+n+1,cmp);
sta[top=1]=a[1];
for (int i=2;i<=n;++i) {
while (top>1 && cross(sta[top-1],sta[top],a[i])<=0) --top; // here
sta[++top]=a[i];
}
if (top<=4) {
double ans=0;
if (top>2) ans=cross(sta[1],sta[2],sta[3]);
if (top==4) ans+=cross(sta[1],sta[3],sta[4]);
ans/=2;
printf("%.3lf\n",ans);
return 0;
}
double ans=0;
for (int i=1;i<=top-2;++i) {
int j=(i+1)%top+1,k=i%top+1,l,id=j%top+1;
double s1=cross(sta[i],sta[k],sta[j])/2;
double s2=0;
for (l=id;l!=i;l=l%top+1) {
double tmp=cross(sta[i],sta[j],sta[l])/2;
if (tmp>s2) s2=tmp,id=l;
}
l=id;
ans=max(ans,s1+s2);
for (j=j%top+1;j%top+1!=i;j=j%top+1) {
s1=cross(sta[i],sta[k],sta[j])/2; // here
s2=cross(sta[i],sta[j],sta[l])/2; // here
if (l==j) l=l%top+1,s2=cross(sta[i],sta[j],sta[l])/2;
while (k%top+1!=j && cross(sta[i],sta[k%top+1],sta[j])/2>s1) k=k%top+1,s1=cross(sta[i],sta[k],sta[j])/2;
while (l%top+1!=i && cross(sta[i],sta[j],sta[l%top+1])/2>s2) l=l%top+1,s2=cross(sta[i],sta[j],sta[l])/2;
ans=max(ans,s1+s2);
}
}
printf("%.3lf\n",ans);
}