POJ2187 旋转卡壳 求最长直径

给定平面上的一些散点集，求最远两点距离的平方值。

题解：

旋转卡壳求出凸包，然后根据单调性，求出最远两点的最大距离

 #pragma GCC optimize(2)

 #pragma G++ optimize(2)

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define eps 0.00000001

 #define N 50007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,top;

 double ans;

 double sqr(double x){return x*x;}

 struct P

 {

     double x,y;

     P(){}

     P(double _x,double _y):x(_x),y(_y){}

     friend P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}

     friend P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}

     friend double operator*(P a,P b){return a.x*b.y-a.y*b.x;}

     friend double operator/(P a,P b){return a.x*b.x+a.y*b.y;}

     friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}

     friend bool operator!=(P a,P b){return !(a==b);}

     friend bool operator<(P a,P b)

     {

         if(fabs(a.y-b.y)<eps)return a.x<b.x;

         return a.y<b.y;

     }

     friend double dis2(P a){return sqr(a.x)+sqr(a.y);}

     friend void print(P a){printf("%.2lf %.2lf\n",a.x,a.y);}

 }p[N],q[N];

 bool cmp(P a,P b)

 {

     if(fabs((b-p[])*(a-p[]))<eps)return dis2(a-p[])<dis2(b-p[]);

     return (a-p[])*(b-p[])>;//叉乘大于0，表示向左转，a的斜率更小。

 }

 void Graham()//选出凸包上的点。

 {

     for (int i=;i<=n;i++)

         if(p[i]<p[])swap(p[i],p[]);

     sort(p+,p+n+,cmp);

     q[++top]=p[],q[++top]=p[];

     for (int i=;i<=n;i++)

     {

         while((q[top]-q[top-])*(p[i]-q[top-])<eps&&top>)top--;//如果当前的点的斜率更小，就替换

         q[++top]=p[i];

     }

 }

 void RC()//求直径。

 {

     q[top+]=q[];//因为凸包是一个圈。

     int now=;

     for (int i=;i<=top;i++)

     {

         while((q[i+]-q[i])*(q[now]-q[i])<(q[i+]-q[i])*(q[now+]-q[i]))

         {

             now++;

             if(now==top+)now=;

         }

         ans=max(ans,dis2(q[now]-q[i]));

     }

 }

 int main()

 {

     n=read();

     for (int i=;i<=n;i++)

         p[i].x=read(),p[i].y=read();

     Graham();

     RC();

     printf("%d",(int)ans);

 }