先求出凸包，時間復雜度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.yx2*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; itu[i].y)minn=i;
if(tu[maxx].y
