题目

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

分析

最暴力的想法是枚举四个点，然而肯定超时。接着不知道怎么想到中途相遇，然而一点关系都没有。这里用到了一个单调性： 如果在凸包上确定了一个点\(x\)，令\(x\)逆时针方向的第一个点为\(y\)，这时确定了一个点\(z\)使得\(S_{\triangle XYZ}最大，那么当\)y\(逆时针移动的时候，使得三角形面积最大的点\)z\(就会不动或逆时针移动。这个性质发展成为我们说的旋转卡壳。 这就是说，如果在凸包上确定了一个点，那么我们可以\)O(n)\(求出包含这个点的所有凸包上的四边形的最大面积。 所以我们可以枚举所有点，在\)O(n^2)$中求出答案。

代码

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

求凸包极角排序的时候，选择的基础点一定是最下面，最左边的，而不可以仅仅是最下面的，否则会出现\(0\)和\(-0\)这种情况。在求凸包单调栈弹出的时候，要用小于等于号，否则如果有重点的情况就会出现问题。在计算答案时，每次移动\(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); }

转载于:https://www.cnblogs.com/owenyu/p/6724687.html