求点对之间的最长距离或者说是凸包的直径，在Andrew算法的基础上，使用旋转卡壳来求解。
旋转卡壳主要通过双指针进行扫描，维护两个指针分别指向凸包上的两个点，计算它们之间的距离，并根据叉乘的符号来移动指针。
以下以P1452 Beauty Contest G为例。
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct p{
double x,y;
}pos[50006],s[2*50006];
double dis(p a,p b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double check(p a,p b,p c){
return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
bool cmp(p a, p b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>pos[i].x>>pos[i].y;
}
sort(pos+1,pos+n+1,cmp);
int top=0;
for(int i=1;i<=n;++i){
while(top>1&&check(s[top-1],s[top],pos[i])<=0){
top--;
}
s[++top]=pos[i];
}
int temp=top;
for(int i=n-1;i>0;--i){
while(top>temp&&check(s[top-1],s[top],pos[i])<=0){
top--;
}
s[++top]=pos[i];
}
top--;
double ans=0;
if(top==2){
ans=dis(s[1],s[2]);
}
else{
for(int i=1;i<=top;++i){
s[i+top]=s[i];
}
int j=2;
for(int i=1;i<=top;++i){
while(fabs(check(s[i],s[i+1],s[j]))<fabs(check(s[i],s[i+1],s[j+1]))){
j++;
}
ans=max(ans,dis(s[i],s[j]));
ans=max(ans,dis(s[i+1],s[j]));
}
}
cout<<(long long)(ans*ans)<<endl;
}