旋转卡壳学习笔记

　　旋转卡壳属于计算几何内容，用于求平面最远点对。

　　首先，易证最远点对一定是凸包上的两个点，对于平面上n个点，先使用graham扫描法求出凸包上所有的点，复杂度$O(nlogn)$。随后，假设最远的点对为点m,n，点m到与n的距离最远，设点n在凸包上的两条边为l1与l2，记m到直线l1,l2距离为dis(m,l1)和dis(m,l2)，则点n到边l1或l2的距离一定是凸包上最远的，凸包不存在其他的点到凸包上的某条边距离大于它。即max(dis(m,l1),dis(m,l2))>=dis(p,l)，其中p为凸包上的点，l为凸包上的边。这一点看了很多的博客，都写的易证，我上周证了两天愣是没证出来，有能帮忙解答的欢迎留言，万分恳求有大神来帮忙解释。

　　随后，就是旋转卡壳的精髓，对于边l1，若距离最远的点为p1,当搜索到l1逆时针方向上的点l2时，距离l2最远的点位p1或p1逆时针方向上的点p2，即max(dis(l2,p1),dis(l2,p2))>=dis(l2,p)，p为凸包上任意的点。因此，只需要在逆时针枚举边的时候同时将所对应的点也逆时针方向移动即可。

　　例题poj2187，这道题数据可能是随机的，点虽然多，但是计算出的凸包上的点数量非常少，实际上枚举凸包上任意两点距离即可，但对于4e5数据大小极限复杂度$O(n^{2})$，完全可以构造数据，所有点都是凸包上的点，将其卡掉，所以旋转卡壳才是正解。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int ,int> pii;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rept(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
#define mes(a,b) memset(a,b,sizeof a)
const int inf= 0x3f3f3f3f;
const int maxn=5e4+5;

pii point[maxn];//存放点，下标从0开始
double dis(const pii &s1,const pii &s2)
{
    return sqrt((s1.fi-s2.fi)*(s1.fi-s2.fi)+(s1.se-s2.se)*(s1.se-s2.se));
}
ll powdis(const pii &s1,const pii &s2)
{
    return ((ll)s1.fi-s2.fi)*(s1.fi-s2.fi)+(s1.se-s2.se)*(s1.se-s2.se);
}

pii operator -(const pii &s1,const pii &s2)
{
    return mp(s1.fi-s2.fi,s1.se-s2.se);
}
int s[maxn];//栈 
int chaji(const pii &s1,const pii &s2)//差积 
{
    return s1.fi*s2.se-s1.se*s2.fi;
}
bool comp(const pii &s1,const pii &s2)
{
    int x=chaji(s1-point[0],s2-point[0]);
    if( x>0|| (x==0&&fabs(s1.fi-point[0].fi)<fabs(s2.fi-point[0].fi)) ) return 1;
    else return 0;
}

double sqare(const pii &a,const pii &b,const pii &c)
{
    return 0.5*abs( (b.fi-a.fi)*(c.se-a.se)-(c.fi-a.fi)*(b.se-a.se));
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n,cnt=0;//n为点个数，cnt为凸包点个数 
    cin>>n;
    rep(i,0,n) cin>>point[i].fi>>point[i].se;
    if(n==2)
    {
        cout<<powdis(point[0],point[1])<<"
";
        return 0;
    }
    int p=0;
    rep(i,1,n)
        if( point[i].se<point[p].se||(point[i].se==point[p].se&&point[i].fi<point[p].fi) )
            p=i;
    swap(point[0],point[p]);
    sort(point+1,point+n,comp);
    s[cnt++]=0;
    s[cnt++]=1;
    rep(i,2,n)
    {
        while(cnt>=2&&chaji( point[s[cnt-1]]-point[i],point[s[cnt-2]]-point[i] )>=0 ) cnt--;
        s[cnt++]=i;
    }
    ll ans=0;
    p=2;
    rep(i,0,cnt)
    {
        while(sqare(point[s[i]],point[s[(i+1)%cnt]],point[s[p]])<sqare(point[s[i]],point[s[(i+1)%cnt]],point[s[(p+1)%cnt]]))
            p=(p+1)%cnt;
        ans=max(ans,powdis(point[s[i]],point[s[p]]));
        ans=max(ans,powdis(point[s[(i+1)%cnt]],point[s[p]]));
        ans=max(ans,powdis(point[s[i]],point[s[(p+1)%cnt]]));
        ans=max(ans,powdis(point[s[(i+1)%cnt]],point[s[(p+1)%cnt]]));
    }
    
    cout<<ans<<endl;
    return 0;
}