旋转卡壳部分模板

凸包直径

旋转卡壳凸包直径详解

//计算凸包直径，输入凸包ch，顶点个数为n，按逆时针排列，输出直径的平方

int rotating_calipers(int n)
{
    int q = 1;
    int ans = 0;
    ch[n] = ch[0];
    for(int i = 0 ; i < n;  i++)
    {
        while(mul(ch[i+1],ch[q+1],ch[i])>mul(ch[i+1],ch[q],ch[i]))//枚举凸包一条边并扫描其它点，通过计算三角形面积的方法找到最远的点
        q = (q+1)%n;
        ans = max(ans,max(dis(ch[i]-ch[q]),dis(ch[i+1]-ch[q+1])));
    }    
    return ans;
}

 凸包间最小距离

struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {} //构造函数 方便代码编写
}p[N],q[N];
typedef Point pointt;
pointt operator + (Point a,Point b)
{
    return Point(a.x+b.x,a.y+b.y);
}
pointt operator - (Point a,Point b)
{
    return Point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
bool operator == (const Point &a,const Point &b)
{
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(Point a,Point b)
{
    return a.x*b.x+a.y*b.y;
}
double  dis(Point a)
{
    return sqrt(dot(a,a));
}
double cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
void anticlock(Point p[],int n)//逆时针排序
{
    for(int i = 0 ; i < n-2 ; i++)
    {
        double k = cross(p[i+1]-p[0],p[i+2]-p[0]);
        if(dcmp(k)>0) return ;
        else if(dcmp(k)<0)
        {
            reverse(p,p+n);
            return ;
        }
    }
}
double distoline(Point a,Point b,Point c)//点到线段ab的最短距离
{
    if(dcmp(dis(a-b))==0) return dis(a-c);
    if(dcmp(dot(a-b,a-c))<0) return dis(a-c);
    if(dcmp(dot(b-a,b-c))<0) return dis(b-c);
    return fabs(cross(a-b,a-c))/dis(a-b);
}
double dist(Point a,Point b,Point c,Point d)//线段ab和cd间的最短距离
{
    double ans = distoline(a,b,c);
    ans = min(ans,distoline(a,b,d));
    ans = min(ans,distoline(c,d,a));
    ans = min(ans,distoline(c,d,b));
    return ans;
}
double mul(Point a,Point b,Point c)
{
    return cross(b-a,c-a);
}
double  solve(Point p[],int n,Point q[],int m)
{
    int i;
    int miny = 0,maxy = 0;
    for(i = 0;i < n; i++)
    {
        if(p[i].y<p[miny].y)
        miny = i;
    }
    for(i =0 ; i< m ; i++)
    if(q[i].y>q[maxy].y) maxy = i;
    double ans = dis(p[miny]-q[maxy]);
    for(i = 0 ;i < n; i++)
    {
        double tmp;
        while(tmp = mul(p[miny],p[miny+1],q[maxy+1])-mul(p[miny],p[miny+1],q[maxy])>eps)
        maxy = (maxy+1)%m;
        if(dcmp(tmp)>0) ans = min(ans,distoline(p[miny],p[miny+1],q[maxy]));
        else
        ans = min(ans,dist(p[miny],p[miny+1],q[maxy],q[maxy+1]));//边-边
        miny = (miny+1)%n;
    }
    return ans;
}