LINK：旋转卡壳
如题 是一道模板题。
容易想到n^2暴力 当然也能随机化选点 (还真有人过了
考虑旋转卡壳 其实就是对于某个点来说找到其最远的点。
在找的过程中需要借助一下个点的帮助 利用当前点到当前线段的所构成的面积来判断高度是否足够高。
容易证明第二个指针最多跑两圈 第一个指针跑一圈 所以复杂度O(n).
不过求凸包是nlogn的。
值得一提的是 当高度相同时 此时最多会出现两个点 然而这两个点都有可能成为答案 所以都要更新.
const int MAXN=50010;
struct Vec
{
db x,y;int id;Vec(){}Vec(db _x,db _y){x=_x;y=_y;}
inline Vec operator +(Vec b){return Vec(x+b.x,y+b.y);}
inline Vec operator -(Vec b){return Vec(x-b.x,y-b.y);}
inline Vec operator -(){return Vec(-x,-y);}
inline db operator *(Vec b){return x*b.x+y*b.y;}//点积
inline db operator %(Vec b){return x*b.y-b.x*y;}//叉积
inline db operator ~(){return x*x+y*y;}//模长的平方
inline bool operator ==(Vec b){return fabs(x-b.x)<=EPS&&fabs(y-b.y)<=EPS;}
inline bool operator !=(Vec b){return fabs(x-b.x)>EPS||fabs(y-b.y)>EPS;}
inline Vec Unit(){db _=sq(x*x+y*y);return Vec(x/_,y/_);}//单位化
inline Vec Norm(){db _=sq(x*x+y*y);return Vec(-y/_,x/_);}//单位法向量
inline bool Quad(){return y>EPS||(fabs(y)<=EPS&&x>=-EPS);}
inline bool operator <(Vec b){return fabs(y-b.y)<=EPS?x<b.x:y<b.y;}
};typedef Vec pt;
inline Vec operator /(Vec a,db k){return Vec(a.x/k,a.y/k);}
inline Vec operator *(db k,Vec a){return Vec(a.x*k,a.y*k);}
inline Vec operator *(Vec a,db k){return Vec(a.x*k,a.y*k);}
inline bool para(Vec a,Vec b){return fabs(a%b)<=EPS;}//判断a b是否平行
inline bool Toleft(Vec a,Vec b){return b%a>EPS;}//判断a是否在b的左边
inline void O(pt a,char c=' '){printf("(%.3lf,%.3lf)%c",a.x,a.y,c);}
int n,top,ans;
pt a[MAXN],s[MAXN],LTL;
int w1[MAXN],w2[MAXN];
inline bool cmpltl(pt a,pt b){return para(a=a-LTL,b=b-LTL)?~a<~b:Toleft(b,a);}
inline int dis(int x,int y){return pf(w1[x]-w1[y])+pf(w2[x]-w2[y]);}
inline void RC()
{
s[top+1]=s[1];
for(int i=1,j=2;i<=top;++i)
{
while((s[i+1]-s[i])%(s[j]-s[i])<(s[i+1]-s[i])%(s[j+1]-s[i]))j=j%top+1;
ans=max(ans,dis(s[i].id,s[j].id));ans=max(ans,dis(s[i].id,s[j+1].id));
}
return;
}
signed main()
{
//freopen("1.in","r",stdin);
gt(n);
rep(1,n,i)
{
gt(w1[i]);gt(w2[i]);
a[i].x=w1[i];
a[i].y=w2[i];
a[i].id=i;
}
LTL=*min_element(a+1,a+1+n);
sort(a+1,a+1+n,cmpltl);
rep(1,n,i)
{
while(top>1&&!Toleft(a[i]-s[top-1],s[top]-s[top-1]))--top;
s[++top]=a[i];
}
RC();put(ans);
return 0;
}