Squares

【题目链接】

【题目类型】旋转卡壳

&题解：

听着算法名字,感觉挺难,仔细一看之后,发现其实很简单,就是依靠所构成三角行面积来快速的找对踵点,就可以省去很多的复杂度了.旋转的复杂度是O(n),之后还有计算每条边对应的对踵点复杂度平均大约O(n/2)在实际中也许可以更快

&代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct Point {    int x,y;    Point(int x=0,int y=0): x(x),y(y) {}};typedef Point Vector;Vector operator - (const Vector& A,const Vector& B) {return Vector(A.x-B.x , A.y-B.y);}bool operator == (const Point& a,const Point& b) {return a.x==b.x&&a.y==b.y;}bool operator < (const Point& a,const Point& b) {return a.x
         
          
            ConvexHull(vector
           
             p) { sort(p.begin(),p.end()); p.erase(unique(p.begin(),p.end()) , p.end()); int n=p.size(), m=0; vector
            
              ch(n+1); for(int i=0; i
             
              1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2; i>=0; i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } if(m>1) m--; ch.resize(m); return ch;}int diameter2(vector
              
               & points) { vector
               
                 p=ConvexHull(points); int n=p.size(); if(n==1) return 0; if(n==2) return Dist2(p[0] , p[1]); p.push_back(p[0]); int ans=0; for(int u=0, v=1; u
                
                  po; for(int i=0; i