ICPC2019台北L-Largest Quadrilateral（求凸包+单调队列）

文章目录

题目链接模板题意题解AC代码

题目链接

https://codeforces.com/gym/102460/attachments

模板

这个题可以学会O(nlogn)求外围凸包的模板。

题意

给一堆点，选出四个点使得按某种顺序连接这4个点的四边形面积最大。点数是4096，大概是n方的复杂度。

题解

首先这个最大的四边形应该是个凸四边形。只有当最大凸包上只有3个点时才可能是凹四边形。如果是图凸包只有3个点，那就随便乱搞了。凸包上的3个点必选，我是枚举剩下不在凸包上的点作为第四个点，完了看看哪种连接顺序面积最大就完了。这个复杂度显然是$O(n)$的。主要难点是一般情况。大概的思路是枚举凸包上的两个点确定一条边，然后在这条边的两边分别各自找到一点，使得这个点和这条边形成的三角形面积最大。暴力做法是$O(n^3)$，不太行。如果按某种顺序枚举边，就可能使得答案点的决策单调，就可以单调队列。枚举边可以按照与第一个点的极角逆时针枚举，这样决策的点也会逆时针旋转，所以在O(n)枚举边的第二个点的同时，决策三角形第三的答案也同时确定。总复杂度$O(n^2)$。另外，double好像会出锅。因为只可能是整数或.5的小数。所以改成long long就过了。

AC代码

凸包的板子是网上白剽的。

#include<bits/stdc++.h> using namespace std; const int MaxN=10010; int n,tot;//n?????,tot?????? struct point { long long x,y; }; point p[MaxN],CHP[MaxN],a[MaxN];//CHP?????????? bool cmp(point a,point b)//????,?x?????,??x??,?y?????? { return (a.x<b.x||(a.x==b.x&&a.y<b.y)); } long long xmul(point a,point b,point c)//?? { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } void Andrew() { sort(p,p+n,cmp); tot=0; for(int i=0;i<n;++i)//??????? { while(tot>1&&xmul(CHP[tot-2],CHP[tot-1],p[i])<0) --tot; CHP[tot++]=p[i]; } int k=tot; for(int i=n-2;i>=0;--i)//??????? { while(tot>k&&xmul(CHP[tot-2],CHP[tot-1],p[i])<0) --tot; CHP[tot++]=p[i]; } if(n>1)//?????????????? --tot; } //long long odist(int i,int j){ // return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)); //} //long long dist(int dian,int i,int j){ // long long A=a[i].y-a[j].y; // long long B=a[i].x-a[j].x; // long long C=0-A*a[i].x-B*a[i].y; // long long mo=sqrt(A*A+B*B); // return (A*a[dian].x+B*a[dian].y+C)/mo; //} long long chaji(int i,int j,int k){ long long x_1=a[i].x-a[j].x; long long y_1=a[i].y-a[j].y; long long x_2=a[i].x-a[k].x; long long y_2=a[i].y-a[k].y; return abs(x_1*y_2-x_2*y_1); } long long chajii(point i,point j,point k){ long long x_1=i.x-j.x; long long y_1=i.y-j.y; long long x_2=i.x-k.x; long long y_2=i.y-k.y; return abs(x_1*y_2-x_2*y_1); } const double eps=1e-6; int noton(int x){ for(int i=1;i<=tot;i++){ if(fabs(a[i].x-p[x].x)==0&&fabs(a[i].y-p[x].y)==0 )return 0; } return 1; } int main() { int t; scanf("%d",&t); while(t--){ memset(p,0,sizeof(p)); memset(CHP,0,sizeof(CHP)); memset(a,0,sizeof(a)); scanf("%d",&n); for(int i=0;i<n;++i) { scanf("%lld%lld",&p[i].x,&p[i].y); } Andrew(); for(int i=0;i<tot;++i) { a[i+1]=CHP[i]; a[i+1+tot]=CHP[i]; } if(tot<=3){ long long ans=0; for(int i=1;i<=n;i++){ if(noton(i)){ long long jian=min( min(chajii(p[i],a[1],a[2]),chajii(p[i],a[1],a[3])) ,chajii(p[i],a[2],a[3])); ans=max(ans,chajii(a[1],a[2],a[3])-jian); } } if(ans%2)printf("%lld.5\n",ans/2); else printf("%lld\n",ans/2); } else{ long long ans=0; for(int i=1;i<=tot;i++){ int l=i,r=i; for(int j=i+1;j<=tot;j++){ r=max(r,j); long long lastr=0; while(r<=i+tot){ long long ss=chaji(r,i,j); if(ss<lastr){r--;break;} lastr=ss; r++; } if(r>i+tot)r--; l=max(l,i); long long lastl=0; while(l<=j){ long long ss=chaji(l,i,j); if(ss<lastl){l--;break;} lastl=ss; l++; } if(l>j)l--; //printf("%d %d %d %d %lf %lf\n",i,j,l,r,lastl,lastr); ans=max(ans,lastl+lastr); } } if(ans%2)printf("%lld.5\n",ans/2); else printf("%lld\n",ans/2); } } return 0; }