【POJ 2187】Beauty Contest（凸包直径、旋转卡壳）

给定点集的最远两点的距离。

先用graham求凸包。旋（xuán）转（zhuàn）卡（qiǎ）壳（ké）求凸包直径。

ps：旋转卡壳算法的典型运用

http://blog.****.net/hanchengxi/article/details/8639476。

 #include <cstdio>
 #include <cmath>
 #include <algorithm>
 #define sqr(x) (x)*(x)
 #define  N 50001
 using namespace std;
 struct P{
     int x,y;
 }p[N],q[N];
 int n,ans,top;
 int dis2(P a,P b){
     return sqr(a.x-b.x)+sqr(a.y-b.y);
 }
 int xmult(P a,P b,P o){
     return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
 }
 int cmp(P a,P b){
     return xmult(a,b,p[])>||xmult(a,b,p[])==&&dis2(a,p[])<dis2(b,p[]);
 }
 void graham(){
     sort(p+,p++n,cmp);
     q[]=p[],q[]=p[];
     top=;
     for(int i=;i<=n;i++){
         while(xmult(q[top],p[i],q[top-])<=&&top>)top--;
         q[++top]=p[i];
     }
 }
 void qiake(){
     q[top+]=q[];
     int now=;
     for(int i=;i<=top;i++){
         while(xmult(q[i+],q[now],q[i])<xmult(q[i+],q[now+],q[i]))
         {
             now++;
             if(now>top)now=;
         }
         ans=max(ans,dis2(q[now],q[i]));
     }
 }
 int main() {
     scanf("%d",&n);
     int t=;
     for(int i=;i<=n;i++){
         scanf("%d%d",&p[i].x,&p[i].y);
         if(p[t].y>p[i].y||p[t].y==p[i].y&&p[t].x>p[i].x)t=i;
     }
     swap(p[],p[t]);
     graham();
     qiake();
     printf("%d",ans);
     return ;
 }