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

 

题解：

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

 

1 #pragma GCC optimize(2) 2 #pragma G++ optimize(2) 3 #include
     
       4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8  9 #define eps 0.0000000110 #define N 5000711 using namespace std;12 inline int read()13 {14     int x=0,f=1;char ch=getchar();15     while(!isdigit(ch)){
   if(ch=='-')f=-1;ch=getchar();}16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}17     return x*f;18 }19 20 int n,top;21 double ans;22 23 double sqr(double x){
   return x*x;}24 struct P25 {26     double x,y;27     P(){}28     P(double _x,double _y):x(_x),y(_y){}29     friend P operator+(P a,P b){
   return P(a.x+b.x,a.y+b.y);}30     friend P operator-(P a,P b){
   return P(a.x-b.x,a.y-b.y);}31     friend double operator*(P a,P b){
   return a.x*b.y-a.y*b.x;}32     friend double operator/(P a,P b){
   return a.x*b.x+a.y*b.y;}33     friend bool operator==(P a,P b){
   return fabs(a.x-b.x)
          
           
            0;//叉乘大于0，表示向左转，a的斜率更小。48 }49 void Graham()//选出凸包上的点。50 {51 for (int i=1;i<=n;i++)52 if(p[i]
            
             1)top--;//如果当前的点的斜率更小，就替换58 q[++top]=p[i];59 }60 }61 void RC()//求直径。62 {63 q[top+1]=q[1];//因为凸包是一个圈。64 int now=2;65 for (int i=1;i<=top;i++)66 {67 while((q[i+1]-q[i])*(q[now]-q[i])<(q[i+1]-q[i])*(q[now+1]-q[i]))68 {69 now++;70 if(now==top+1)now=1;71 }72 ans=max(ans,dis2(q[now]-q[i]));73 }74 }75 int main()76 {77 n=read();78 for (int i=1;i<=n;i++)79 p[i].x=read(),p[i].y=read();80 Graham();81 RC();82 printf("%d",(int)ans);83 }