POJ2187 Beauty Contest 计算几何+旋转卡壳
思路:
本人自己写了一个傻逼的不能再傻逼的御用凸包模板,谁要是扒的话简直就是作死...
然后这道题目主要就是利用旋转卡壳寻找对踵点,然后更新答案.
然后旋转卡壳非常牛逼是\(O(n)\)的.这是为什么呢?
对于凸包上的每一条边,对踵点与这条边形成的三角形的面积必定最大.因此,这条边之外的点是成一个单峰函数分布的.
此外我们还很容易从凸包上得到单调性.
利用这两个性质,就很容易做到凸包上的线性扫描了.
#include<set> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define N 50010 struct Point{ int x,y; Point(){} Point(int _x,int _y):x(_x),y(_y){} bool operator<(const Point&B)const{return(x<B.x)||(x==B.x&&y>B.y);} Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);} Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);} }P[N];int cnt; inline int Cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;} inline int sqr(int x){return x*x;} inline int dis2(const Point&a,const Point&b){return sqr(a.x-b.x)+sqr(a.y-b.y);} set<Point>S; Point stk[N];int top; #define f(x) (x>top?1:x) int main(){ //freopen("tt.in","r",stdin); int n;scanf("%d",&n);register int i,j; if(n<=1){puts("0");return 0;} int x,y; while(n--){scanf("%d%d",&x,&y);if(S.find(Point(x,y))==S.end())S.insert(Point(x,y)),P[++cnt]=Point(x,y);} sort(P+1,P+cnt+1); bool allline=1; for(i=1;i+2<=cnt;++i)if(Cross(P[i]-P[i+1],P[i+1]-P[i+2])!=0)allline=0; if(allline){printf("%d",dis2(P[1],P[cnt]));return 0;} int revins;for(revins=cnt;revins!=1&&P[revins].x==P[revins-1].x;--revins); for(i=revins;i<=(n+revins)/2;++i)swap(P[i],P[n+revins-i]); for(i=1;i<=cnt;++i){ if(!top)stk[++top]=P[i]; else{while(top>1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];} } int nowtop=top; for(i=revins-1;i>=1;--i){ if(top==nowtop)stk[++top]=P[i]; else{while(top>nowtop+1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];} }--top; int r=2,res=0; for(i=1;i<=top;++i){ while(Cross(stk[i]-stk[f(i+1)],stk[i]-stk[r])<=Cross(stk[i]-stk[f(i+1)],stk[i]-stk[f(r+1)]))r=f(r+1); res=max(res,dis2(stk[i],stk[r])); res=max(res,dis2(stk[f(i+1)],stk[r])); } printf("%d",res); return 0; }