令人窒息啊
知乎上说“旋转卡壳”有24种读法
感觉好可怕啊
旋转卡壳模板题
求出凸包后
通过不断的枚举当前的边和对面的点不断得到更优的解
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<cstdlib>
using namespace std;
int n,m,ans;
inline int read(){
char ch=getchar();
int res=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
};
struct point{
int x,y;
point(){}
point(int a,int b):
x(a),y(b){};
friend inline point operator -(const point &a,const point &b){
return point(a.x-b.x,a.y-b.y);
}
friend inline int operator *(const point &a,const point &b){
return a.x*b.y-a.y*b.x;
}
inline int calc(){
return x*x+y*y;
}
}p[50005],q[50005];
inline bool comp(point a,point b){
int res=(a-p[1])*(b-p[1]);
if(res!=0)return res>0;
return a.calc()<b.calc();
}
inline void graham(){
int dat=1;
for(int i=2;i<=n;i++){
if(p[i].x<p[dat].x||(p[i].x==p[dat].x&&p[i].y<p[dat].y)){
dat=i;
}
}
if(dat!=1) swap(p[dat],p[1]);
sort(p+2,p+1+n,comp);
q[++m]=p[1];
for(int i=2;i<=n;i++){
while(m>=2&&((p[i]-q[m-1])*(q[m]-q[m-1])>=0))m--;
q[++m]=p[i];
}
}
inline int area(point a,point b,point c){
return (b-a)*(c-a);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
graham();
if(m==2) {
cout<<(q[2]-q[1]).calc();
return 0;
}
q[m+1]=q[1];
for(int i=1,j=3;i<=m;i++){
while((j)%m+1!=i&&area(q[i],q[i+1],q[j])<=area(q[i],q[i+1],q[j+1])) j=(j)%m+1;
ans=max(ans,(q[j]-q[i]).calc());
ans=max(ans,(q[j]-q[i+1]).calc());
}
cout<<ans<<'\n';
}