@[calms](/user/328935)
给组数据理解一下
```cpp
3
1 2
2 3
3 4
```
答案应该是8
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int x,y,id;
}p[50005];
int l;
node top[50005];
bool use[50005];
bool cmp(node a,node b){
if(a.x==b.x){
return a.y<b.y;
}else{
return a.x<b.x;
}
}
int dot(node a,node b){
return a.x*b.x+a.y*b.y;
}
int cross(node a,node b){
return a.x*b.y-a.y*b.x;
}
int Len(node a){
return dot(a,a);
}
node operator -(node a,node b){
return node{a.x-b.x,a.y-b.y};
}
int main(){
// freopen("1.in","r",stdin);
// freopen("2.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
}
if(n==1){
cout<<0;
return 0;
}
sort(p+1,p+1+n,cmp);
p[1].id=1;
top[++l]=p[1];
for(int i=2;i<=n;i++){
p[i].id=i;
while(l>1&&cross(top[l]-top[l-1],p[i]-top[l])<=0){
use[top[l--].id]=0;
}
top[++l]=p[i];
use[i]=1;
}
int k=l;
for(int i=n-1;i>=1;i--){
if(use[i])continue;// 1.use标记要加上，不然凸包内有重复点旋转卡壳就卡死了
while(l>k&&cross(top[l]-top[l-1],p[i]-top[l])<=0){
use[top[l--].id]=0;
}
top[++l]=p[i];
use[i]=1;
}
if(l==3){// 2.andrew算法求出来的凸包会包含起始点两遍，也就是top[1]跟top[l](后面那个l是字母，前面那个是数字)一样，凸包大小==3的时候实际上还是只有两个点
printf("%d\n",Len(top[2]-top[1]));
return 0;
}
int j=3;
int ans=0;
for(int i=1;i<l;i++){
ans=max(ans,Len(top[i+1]-top[i]));
while(abs(cross(top[j]-top[i],top[i+1]-top[i]))<abs(cross(top[j+1]-top[i],top[i+1]-top[i]))){
++j;
if(j==l) j=1;// 3.如1.和2.中所述，凸包首尾是一个点，如果只是%l+1就会出现旋转卡壳卡死的情况
// cout<<j<<endl;
}
ans=max(ans,max(Len(top[j]-top[i]),Len(top[j]-top[i+1])));
}
printf("%d\n",ans);
return 0;
}
```
by LoserKugua @ 2023-09-12 15:05:07