先求出凸包，时间复杂度O(n*log(n))
然后运用旋转卡壳发求出凸包的直径。
旋转卡壳法：
1.先求出y坐标最大的点为maxx，y最小的点为minn。
2.过minn，，maxx点做一条平行于x轴的直线
3.俩直线分别对minn，maxx点逆时针旋转至某一条直线与凸包的某个点相交为止。
4,用交点更新前一个点。
5,重复3-4直至目前两点都出现过为止。
6,每次旋转之后得到的两点之间的距离的最大值即为凸包的直径
原理：
第一步寻找到的一对点（minn，maxx）一定是一对对踵点。
然后旋转直线会得到另外一对对踵点。
这样一直旋转就会得到所有的对踵点。
然后凸包的直径是某个对踵点直径的距离。
#include<string.h>#include<algorithm>#include<stdlib.h>#include<iostream>#include<stdio.h>#include<vector>#define INF 1000000using 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<b.y;return a.x<b.x;}int cmp2(struct list a,struct list b){int x1=a.x-node[1].x;int x2=b.x-node[1].x;int y1=a.y-node[1].y;int y2=b.y-node[1].y;if(x1*y2==x2*y1)return len(a,node[1])<len(b,node[1]);return x1*y2>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<ts; i++){if(tu[minn].y>tu[i].y)minn=i;if(tu[maxx].y<tu[i].y)maxx=i;}int s1,s2;s1=minn;s2=maxx;int lens;lens=len(tu[s1],tu[s2]);memset(vis,0,sizeof(vis));while(vis[s1]==0||vis[s2]==0){vis[s1]=vis[s2]=1;int x1=tu[s2].x-tu[(s2+1)%ts].x;int x2=tu[(s1+1)%ts].x-tu[s1].x;int y1=tu[s2].y-tu[(s2+1)%ts].y;int y2=tu[(s1+1)%ts].y-tu[s1].y;if(y1*x2<y2*x1)s2=(s2+1)%ts;//根据叉积判断旋转直线最先碰到哪条边else s1=(s1+1)%ts;lens=max(lens,len(tu[s1],tu[s2]));}cout<<lens<<endl;}int main(){scanf("%d",&n);ts=2;for(int i=1; i<=n; i++)scanf("%d%d",&node[i].x,&node[i].y);sort(node+1,node+n+1,cmp1);sort(node+2,node+n+1,cmp2);tubao();diameter();return 0;}
创造条件,去改变生活,做生活的强者.愿你早日成为生活的强者
