qia ke 还是 ka qiao ？

凸包

对向量 $\vec{a} \times \vec{b}$ 的运算的正负值由 $\vec{a}$ 旋转到 $\vec{b}$ 的角度的 $\cos$ 决定（含正负号）。因此如果 $\vec{a}$ 到 $\vec{b}$ 是逆时针旋转它们的叉积就是正数，否则反之。

那么 $x$ 排序后左右顺序扫一遍上下凸包。对于按顺序构成凸包的向量，一定是顺时针旋转，否则便不符合凸包的定义。因此使用栈来维护，如果出现了逆时针旋转则退栈。

被称作 Graham Scan 算法。

注意一些重复点的细节。

旋转卡壳

用于计算凸包点对的最长距离。考虑枚举一条边，再考虑该边的对踵点（距离该边距离最大点），枚举这样所有的点边对即可获取最长距离。可以 $O(n)$ 扫过，而且误差较小。

注意一些细节，同时特判凸包大小为 $3$ 的情况，这意味着所有点都处于同一直线上。

Code - Beauty Contest

// Code by ajcxsu
// Problem: xuan zhuan qia qiao

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10;
typedef long long ll;
struct P {
    ll x, y;
    P operator + (P b) { return {x+b.x, y+b.y}; }
    P operator - (P b) { return {x-b.x, y-b.y}; }
    ll norm() { return x*x+y*y; }
    double dis() { return sqrt(norm()); }
} p[N], con[N];
ll cross(P a, P b) { return a.x*b.y-a.y*b.x; }
bool cmp(const P &a, const P &b) { return a.x==b.x?a.y<b.y:a.x<b.x; }
inline ll dpow(ll x) { return x*x; }
double dis(P a, P b, P x) {
    return (double)abs(cross(a-x, b-x))/(a-b).dis();
}
int t;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>p[i].x>>p[i].y;
    sort(p+1, p+1+n, cmp);
    for(int i=1; i<=n; i++) {
        while(t>=2 && cross(con[t]-con[t-1], p[i]-con[t-1])>=0) t--;
        con[++t]=p[i]; 
    }
    int t2=t;
    for(int i=n-1; i>=1; i--) {
        while(t>=t2+1 && cross(con[t]-con[t-1], p[i]-con[t-1])>=0) t--;
        con[++t]=p[i]; 
    }
    if(t==3) cout<<(con[1]-con[2]).norm()<<endl, exit(0);
    int nt=1;
    ll ans=0;
    for(int i=1; i<t; i++) {
        while(dis(con[i], con[i+1], con[nt])<=dis(con[i], con[i+1], con[nt+1])) nt=nt%(t-1)+1;
        ans=max({ans, (con[i]-con[nt]).norm(), (con[i+1]-con[nt]).norm()});
    }
    cout<<ans<<endl;
    return 0;
}