旋转卡壳，三种实现方式。

上述中说的三种是方式分别是

1. kuangbin的-容易理解
2. 挑战书上的-容易实现
3. 我的-我的理解

第一种kuangbin板子

class Point
{
public:
    double x,y;
    Point() {}
    Point(double x,double y):x(x),y(y)
    {
    }
    Point operator+ (Point p)
    {
        return Point(add(x,p.x),add(y,p.y));
    }
    Point operator -(Point p)
    {
        return Point(add(x,-p.x),add(y,-p.y));
    }
    Point operator *(double d)
    {
        return Point(x*d,y*d);
    }
    double operator *(Point p)
    {
        return add(x*p.x,y*p.y);//外积
    }
    double operator ^(Point p) //内积
    {
        return add(x*p.y,-y*p.x);
    }
    double det(Point p)
    {
        return add(x*p.y,-y*p.x);
    }
    double len()
    {
        return sqrt(add(x*x,y*y));
    }
};
}
//旋转卡壳，求两点间距离平方的最大值
int rotating_calipers(Point p[],int n)//要求p序列为凸包序列
{
    int ans = 0;
    Point v;
    int cur = 1;
    for(int i = 0; i < n; i++)
    {
        v = p[i]-p[(i+1)%n];
        while((v^(p[(cur+1)%n]-p[cur])) < 0)             cur = (cur+1)%n;
        ans = max(ans,max(dist2(p[i],p[cur]),dist2(p[(i+1)%n],p[(cur+1)%n])));
    }
    return ans;
}

第二种挑战书上的-，不过我现在还是不是非常理解。

double add(double a,double b){//考虑误差的加法运算
    if(abs(a+b)<EPS*(abs(a)+abs(b))) return  0;
    return a+b;
}
class Point{
public:
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){
    }
    Point operator+ (Point p){
        return Point(add(x,p.x),add(y,p.y));
    }
    Point operator -(Point p){
        return Point(add(x,-p.x),add(y,-p.y));
    }
    Point operator *(double d){
        return Point(x*d,y*d);
    }
    double operator *(Point p){
        return add(x*p.x,y*p.y);//外积
    }
    double operator ^(Point p){//内积
        return add(x*p.y,-y*p.x);
    }
    double det(Point p){
     return add(x*p.y,-y*p.x);
    }
    double len(){
        return sqrt(add(x*x,y*y));
    }
};
double dist(Point p1,Point p2)//距离的平方
{
    return add((p1.x-p2.x)*(p1.x-p2.x),(p1.y-p2.y)*(p1.y-p2.y));
}
//旋转卡壳求平面最远点对
//输入: 多边形和顶点个数
//输出: 最远点对距离的平方
//时间复杂度n*logn(求凸包)+n(旋转卡壳)
double rotaing_calipers(P* ps,int pn)
{
    vector<P> qs = convex_hull(ps,pn);//求凸包
    int n=qs.size();
    if(n==2){
        return  dist(qs[0], qs[1]);
    }
    int i=0,j=0;//某个方向的对踵点对
    //求出x轴方向的对踵点对
    for(int k=0;k<n; k++){
        if(!cmp_x(qs[i],qs[k])) i=k;
        if(cmp_x(qs[j],qs[k])) j=k;
    }
    double res=0.0;
    int si=i,sj=j;
    while(i!=sj || j!= si){//将方向逐步旋转180度
        res=max(res,dist(qs[i],qs[j]) );
        // 判断先转到边i -(i+1)的发现方向还是 边j - j+1的法线方向
        if( (qs[(i+1)%n] - qs[i]).det(qs[(j+1)%n] - qs[j] ) < 0 ){ // i,i+1边的法线点是 j
            i=(i+1)%n;//先转到i - (i+1)的法线方向
        }
        else{
            j=(j+1)%n;//先转到j - (j+1)的法线方向
        }
    }
    return res;
}

第三种 根据自己理解写出的，旋转卡壳求出每个边对应的对踵点，更新点对最大距离。

double rotaing_calipers(P* ps,int pn)// 保证输入的已经是凸包且按顺序给出点
    vector<P> qs(ps,ps+pn);
    int n=qs.size();
    if(n==2){
        return  dist(qs[0], qs[1]);
    }
    int j=1;
    double ans=0.0;
    for(int i=0;i<n;++i)
    {
        while( (qs[(i+1)%n]-qs[i]).det( qs[(j+1)%n] - qs[j]) >=0 ) j=(j+1)%n;//找到i-i+1边对应的对踵点j
        ans=max(ans, max(dist(qs[j],qs[i]), dist(qs[j],qs[(i+1)%n] )) );
    }
    return ans;
}