旋转卡壳

#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
const int kMaxN=5e4+1;
struct POINT
{
  int x,y;
}p[kMaxN];
int n;
int sk[kMaxN],cnt;
int ans=-1e15;
int CJ(POINT a,POINT i,POINT j)算叉积
{
  return (i.x-a.x)*(j.y-a.y)-(j.x-a.x)*(i.y-a.y);
}
double Dis(POINT i,POINT j)//算距离
{
  return sqrt((i.x-j.x)*1.0*(i.x-j.x)+(i.y-j.y)*1.0*(i.y-j.y));
}
int Dis2(POINT i,POINT j)//算距离的平方
{
  return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
bool cmp(POINT i,POINT j)//级角排序
{
  int cj=CJ(p[1],i,j);
  if(cj>0)return true;
  if(cj==0&&Dis(i,p[1])<Dis(j,p[1]))return true;
  return false;
}
signed main()
{
cin>>n;
cin>>p[1].x>>p[1].y;
for(int i=2;i<=n;i++)
{
  cin>>p[i].x>>p[i].y;
  if(p[i].y<p[1].y)
  {
    swap(p[i].x,p[1].x);
    swap(p[i].y,p[1].y);
  }
  else if(p[i].y==p[1].y&&p[i].x<p[1].x)
  {
    swap(p[i].x,p[1].x);
    swap(p[i].y,p[1].y);
  }
}
sort(p+2,p+n+1,cmp);
sk[++cnt]=1;//求凸包
for(int i=2;i<=n;i++)
{
  if(cnt>=2&&CJ(p[sk[cnt-1]],p[sk[cnt]],p[i])<=0)cnt--;
  sk[++cnt]=i;
}
if(cnt==2)
{
  cout<<Dis2(p[sk[1]],p[sk[2]]);
  return 0;
}
sk[++cnt]=1;
int j=3;//旋转卡壳
for(int i=1;i<cnt;i++)
{
  while(CJ(p[sk[i]],p[sk[i+1]],p[sk[j]])<=CJ(p[sk[i]],p[sk[i+1]],p[sk[j+1]]))
  {
    j++;
    if(j==cnt+1)j=1;
  }
  ans=max(ans,max(Dis2(p[sk[i]],p[sk[j]]),Dis2(p[sk[i+1]],p[sk[j]])));
}
cout<<ans;
return 0;
}