题链：

题解：

计算几何，凸包，旋转卡壳

一个求凸包直径的裸题，旋转卡壳入门用的。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 50050using namespace std;const double eps=1e-8;int sign(double x){	if(fabs(x)<=eps) return 0;	return x<0?-1:1;}struct Point{	double x,y;	Point(double _x=0,double _y=0):x(_x),y(_y){}	void Read(){scanf("%lf%lf",&x,&y);}};typedef Point Vector;bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}Point D[MAXN],C[MAXN];double GL2(Vector A){//Get_Length^2	return A*A;}double DA(Point P,Point P1,Point P2){//Directed_Area	return (P-P1)^(P-P2);}int Andrew(int dnt){	int cnt=0,k;	sort(D,D+dnt);	dnt=unique(D,D+dnt)-D;	for(int i=0;i
          
           1&&sign((C[cnt-1]-C[cnt-2])^(D[i]-C[cnt-2]))<=0) cnt--; C[cnt++]=D[i]; } k=cnt; for(int i=dnt-2;i>=0;i--){ while(cnt>k&&sign((C[cnt-1]-C[cnt-2])^(D[i]-C[cnt-2]))<=0) cnt--; C[cnt++]=D[i]; } return cnt-(dnt>1?1:0);}double RC_GD(int hnt){//Rotating_Calipers_Get_Diameter if(hnt==1) return 0; if(hnt==2) return GL2(C[1]-C[0]); double Di=0; int j=0; C[hnt]=C[0]; for(int i=0;i