给定点集的最远两点的距离。
先用graham求凸包。旋（xuán）转（zhuàn）卡（qiǎ）壳（ké）求凸包直径。
ps：旋转卡壳算法的典型运用
http://blog.csdn.net/hanchengxi/article/details/8639476。
代码语言：javascript复制 1 #include <cstdio>
2 #include <cmath>
3 #include <algorithm>
4 #define sqr(x) (x)*(x)
5 #define N 50001
6 using namespace std;
7 struct P{
8 int x,y;
9 }p[N],q[N];
10 int n,ans,top;
11 int dis2(P a,P b){
12 return sqr(a.x-b.x) sqr(a.y-b.y);
13 }
14 int xmult(P a,P b,P o){
15 return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
16 }
17 int cmp(P a,P b){
18 return xmult(a,b,p[1])>0||xmult(a,b,p[1])==0&&dis2(a,p[1])<dis2(b,p[1]);
19 }
20 void graham(){
21 sort(p 2,p 1 n,cmp);
22 q[1]=p[1],q[2]=p[2];
23 top=2;
24 for(int i=3;i<=n;i ){
25 while(xmult(q[top],p[i],q[top-1])<=0&&top>1)top--;
26 q[ top]=p[i];
27 }
28 }
29 void qiake(){
30 q[top 1]=q[1];
31 int now=2;
32 for(int i=1;i<=top;i ){
33 while(xmult(q[i 1],q[now],q[i])<xmult(q[i 1],q[now 1],q[i]))
34 {
35 now ;
36 if(now>top)now=1;
37 }
38 ans=max(ans,dis2(q[now],q[i]));
39 }
40 }
41 int main() {
42 scanf("%d",&n);
43 int t=1;
44 for(int i=1;i<=n;i ){
45 scanf("%d%d",&p[i].x,&p[i].y);
46 if(p[t].y>p[i].y||p[t].y==p[i].y&&p[t].x>p[i].x)t=i;
47 }
48 swap(p[1],p[t]);
49 graham();
50 qiake();
51 printf("%d",ans);
52 return 0;
53 }
