POJ2187Beauty Contest 旋转卡壳

题目链接
先求凸包
再求凸多边形直径
旋转卡壳模板题
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #define N 50010
 7 using namespace std;
 8 int n,tp,ans;
 9 struct P{
10     int x,y;
11     bool operator < (const P &b)const{return x==b.x?y<b.y:x<b.x;}
12     P operator - (const P &b)const{return (P){x-b.x,y-b.y};}
13 }a[N],s[N];
14 int dis(P a){return a.x*a.x+a.y*a.y;}
15 int crs(P a,P b){return a.x*b.y-a.y*b.x;}
16 void getbag(){
17     sort(a+1,a+1+n);
18     for(int i=1;i<=n;i++){
19         while(tp>1&&crs(a[i]-s[tp-1],s[tp]-s[tp-1])>=0)--tp;
20         s[++tp]=a[i];
21     }
22     int now=tp;
23     for(int i=n-1;i>=1;i--){
24         while(tp>now&&crs(a[i]-s[tp-1],s[tp]-s[tp-1])>=0)--tp;
25         s[++tp]=a[i];
26     }
27     if(n>1)--tp;
28 }
29 void rotate(){
30     int p=2;s[tp+1]=s[1];
31     for(int i=1;i<=tp;i++){
32         while(crs(s[i+1]-s[i],s[p]-s[i])<crs(s[i+1]-s[i],s[p+1]-s[i]))p=p%tp+1;
33         ans=max(ans,max(dis(s[p]-s[i]),dis(s[p+1]-s[i+1])));
34     }
35 }
36 int main(){
37     scanf("%d",&n);
38     for(int i=1;i<=n;i++)
39     scanf("%d%d",&a[i].x,&a[i].y);
40     getbag();rotate();
41     //for(int i=1;i<=tp;i++)printf("%d %d
",s[i].x,s[i].y);
42     printf("%d
",ans);
43     return 0;
44 }