旋（xuán）转（zhuàn）卡（qia）壳（qiào）
旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解，但是实现起来真的很容易让人“卡壳”。
文章图片
其实简单来说就是用一对平行线“卡”住凸包进行旋转。
被一对卡壳正好卡住的对应点对称为
对踵点，对锺点的具体定义不好说，不过从图上还是比较好理解的。
可以证明对踵点的个数不超过
3N/2个 也就是说对踵点的个数是
O(N)的
对踵点的个数也是我们下面解决问题时间复杂度的保证。
【旋转卡壳(入门)】
卡壳呢，具体来说有两种情况：
1.
文章图片
一种是这样，两个平行线正好卡着两个点；
2.
文章图片
一种是这样，分别卡着一条边和一个点。
而第二种情况在实现中比较容易处理，这里就只研究第二种情况。
在第二种情况中 我们可以看到 一个对踵点和对应边之间的距离比其他点要大（借用某大神的图··）
也就是一个对踵点和对应边所形成的三角形是最大的 下面我们会据此得到对踵点的简化求法。
文章图片
下面给出一个官方的说明：
Compute the polygon's extreme points in the y direction. Call them ymin and ymax. Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum. Rotate the lines until one is flush with an edge of the polygon. A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary. Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again. Output the pair(s) determining the maximum as the diameter pair(s).
文章图片
要是真的按这个实现起来就麻烦到吐了。。
根据上面的第二种情况，我们可以得到下面的方法：
如果qa，qb是凸包上最远两点，必然可以分别过qa，qb画出一对平行线。通过旋转这对平行线，我们可以让它和凸包上的一条边重合,如图中蓝色直线，可以注意到，qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个顶点到该边两个端点的距离，并记录最大的值。
直观上这是一个O(n2)的算法，和直接枚举任意两个顶点一样了。
然而我们可以发现 凸包上的点依次与对应边产生的距离成
单峰函数（如下图：）
文章图片
这个性质就很重要啦。
根据这个凸包的特性，我们注意到逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。这就是所谓的“旋转”吧！
利用旋转卡壳，我们可以在O（n）的时间内得到凸包的对锺点中的长度最长的点对。
又由于最远点对必然属于对踵点对集合 ，那么我们先求出凸包 然后求出对踵点对集合 然后选出距离最大的即可
那么具体的代码就很容易实现了，利用叉积，代码只有这么几行的长度：
double rotateCalipers(Point *ch,int n)
{
double ans=-INF;
ch[n]=ch[0];
int q=1;
for(int i=0;
i对多边形进行旋转卡壳，多边形的边只能有两个点，即不存在三点共线，所以求凸包的时候要注意，不要把共线的点也求进来 其中cross()是计算叉积，因为凸包上距离一条边最远的点和这条边的两个端点构成的三角形面积是最大的。之所以既要更新(ch[q],ch[i])又要更新(ch[q+1],ch[i+1])是为了处理凸包上两条边平行的特殊情况。
ps:为什么是边( q, i )和边( q+1, i+1 )，而不是边( q, i+1 )和边( q+1, i ),动手画画图就知道了
文章图片
Beauty Contest
题意：
求凸多边形直径（最远距离的两点的距离）
题解：
当然是用旋转卡壳啦
#include
#include
#include
#include
using namespace std;
const int MAXN=50010;
const int INF=0x7fffffff;
struct Point
{
double x,y;
Point (double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
Vector operator - (Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool operator <(const Point &a,const Point &b)
{
return a.x1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;
i>=0;
i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double length(Vector A)
{
return A.x*A.x+A.y*A.y;
}
double rotateCalipers(Point *ch,int n)
{
double ans=-INF;
ch[n]=ch[0];
int q=1;
for(int i=0;
i 其实没学旋转恰壳时，我是先求出凸包，然后再枚举任意凸包两点距离暴力过的，
O( n^2)居然不超时
#include
#include
#include
#include
using namespace std;
const int MAXN=50010;
const int INF=0x7fffffff;
struct Point
{
double x,y;
Point (double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
Vector operator - (Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool operator <(const Point &a,const Point &b)
{
return a.x1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;
i>=0;
i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double length(Vector A)
{
return A.x*A.x+A.y*A.y;
}
int main()
{
int n,ans;
double res,len;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;
i
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
