poj-2187-凸包-旋转卡壳法求直径

先求出凸包，时间复杂度O(n)

然后运用旋转卡壳发求出凸包的直径。

旋转卡壳法：

1.先求出y坐标最大的点为maxx，y最小的点为minn。

2.过minn，maxx点做一条平行于x轴的直线

3.俩直线分别对minn，maxx点逆时针旋转至某一条直线与凸包的某个点相交为止。

4,用交点更新前一个点。

5,重复3-4直至目前两点都出现过为止。

6,每次旋转之后得到的两点之间的距离的最大值即为凸包的直径

原理：

第一步寻找到的一对点（minn，maxx）一定是一对对踵点。

然后旋转直线会得到另外一对对踵点。

这样一直旋转就会得到所有的对踵点。

然后凸包的直径是某个对踵点直径的距离。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define INF 1000000 using namespace std; struct list { int x,y; } node[50051],tu[50051]; int ts,n; int vis[50051]; int len(struct list a,struct list b) { int xx=a.x-b.x; int yy=a.y-b.y; return xx*xx+yy*yy; } int cmp1(struct list a,struct list b) { if(a.y!=b.y)return a.y
        
         x2*y1; } void push(int i) { if(ts<=2) { tu[ts++]=node[i]; return ; } int x1=tu[ts-1].x-tu[ts-2].x; int y1=tu[ts-1].y-tu[ts-2].y; int x2=node[i].x-tu[ts-1].x; int y2=node[i].y-tu[ts-1].y; if(x1*y2>x2*y1)tu[ts++]=node[i]; else ts--,push(i); } void tubao() { tu[0]=node[1]; tu[1]=node[2]; for(int i=3; i<=n; i++)push(i); } void diameter() { int minn,maxx; minn=maxx=0; for(int i=0; i
         
          tu[i].y)minn=i; if(tu[maxx].y