计算几何之旋转卡壳代码模板与证明

以你之姓@ 2022-11-10 14:19 273阅读 0赞

### 旋转卡壳 ###

旋转卡壳这个算法很形象，一般用来在 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度下**求最远点对问题**，就是求平面中任意两点的最远距离。  
一般求最远点对问题得枚举两个点，所以复杂度是 O ( n 2 ) O(n^2) O(n2)，而用旋转卡壳来求可以降低这个复杂度。

旋转卡壳就是指用两条平行线来夹住一个凸多边形。我们可以先[求出这些点的凸包][Link 1]，最远点对一定是凸包上的点，可以用三角形证得，然后旋转这两条平行线，旋转过程中始终夹住这个凸包，旋转一周中平行线间的最远距离就是最远点对的距离。  
![eg][]  
如图，当平行线旋转到蓝色直线所在位置时，就是平面上所有点之间最远点对的距离。

### 证明 ###

如果只看做法的话可以跳过证明，看后面的代码模板即可。  
大概的意思大家应该都理解了，但是如何实现呢？怎么用平行线来夹住凸多面体呢？如何枚举角度呢？角度从0°-360°是个无穷的值。  
对于这几个疑问我们可以来看看旋转的过程，这个角度肯定是没法枚举的，所以我们就要把角度离散化，枚举几个关键点。我们将平行线所夹的两个顶点称为**对踵点**，最远点对一定是一组对踵点，而对踵点发生变化的**临界点**就是当平行线和凸多边形的一条边重合的时候。  
![eg][eg 1]  
如图，当**平行线和ab边重合**时，对踵点就从ac变成了bc，所以我们只需要枚举每条边，找到该边对应的两组对踵点ac和bc，然后一直求这两组对踵点的最大距离，不断更新我们的最大值。当枚举完所有边，最终的结果就是最远点对。  
那么还有一个问题，**如何找对踵点**呢？我们可以发现，当逆时针枚举边时，平行线转到下一条边的同时，对踵点只会有两种变化，要么不动，还是c点；要么也逆时针走（从c点逆时针的下一个或下下一个等），他不会往前走，所以是一个**单调的变化**，我们就可以用**双指针**，i指到直线，j指到对踵点，都单调逆时针旋转就ok。我们记c的逆时针的下一个点是d，如果三角形abd面积大于三角形abc的面积，那么j就指到d去，因为这两个三角形是同底的，面积越大说明高越大，即d点到直线ab的距离，用while循环j找到对踵点。  
这也我们就可以枚举所有的边，找到所有对踵点距离最大的，就是最远点对，具体步骤可以看代码模板。

### 代码模板 ###

#include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define x first //方便使用pair
    #define y second
    const int N = 50010;
    typedef pair<int,int> PII;	//用pair来存点
    
    PII p[N];	//p存所有点
    int n,top,stk[N];	//n个点，stk是求凸包的栈
    bool used[N];		//求凸包的数组，判断点是否在边界上
    
    PII operator-(PII a,PII b)	//重载运算符减号，PII间相减
    { 
    	return { a.x-b.x, a.y-b.y};
    }
    
    int operator*(PII a,PII b)	//重载运算符乘，求向量的叉积
    { 
    	return a.x*b.y - a.y*b.x;	//x1*y2 - x2*y1
    }
    
    int area(PII a,PII b,PII c)	//求三角形abc的面积
    { 
    	return (b - a) * (c - a);	//向量的叉积
    }
    
    int lens(PII a,PII b)	//两点间距离
    { 
    	int dx = a.x - b.x;
    	int dy = a.y - b.y;
    	return dx*dx + dy*dy;	//因为求最大距离的平方，所以不用开方
    }
    
    void andrew()		//andrew算法求凸包，凸包模板
    { 
    	sort(p,p+n);
    	for(int i = 0;i < n;i++)
    	{ 	
    		while(top >= 2 && area(p[stk[top-2]],p[stk[top-1]],p[i]) <= 0)	//注意这里要先求下凸壳，因为要逆时针存点，方面我们找对踵点
    		{ 
    			if(area(p[stk[top-2]],p[stk[top-1]],p[i]) < 0)
    				used[stk[top-1]] = 0;
    			top--;
    		}
    		stk[top++] = i;
    		used[i] = 1;
    	}
    	used[0] = 0;
    	for(int i = n-1;i >= 0;i--)
    	{ 
    		if(used[i])
    			continue;
    		while(top >= 2 && area(p[stk[top-2]],p[stk[top-1]],p[i]) <= 0)	//然后再求上凸壳
    			top--;
    		stk[top++] = i;
    	}
    	top--;	//最后的top--是为了把最后一个入栈的0号点去掉
    }
    
    int rotating()	//旋转卡壳
    { 
    	if(top <= 2)	//如果凸包上的点小于等于两个点
    		return lens(p[0],p[n-1]);	//返回第一个点和最后一个点的距离，这里的p是排过序的
    	int ans = 0;	//存最远距离
    	for(int i = 0,j = 2;i < top;i++)	//双指针ij
    	{ 
    		PII a = p[stk[i]],b = p[stk[i+1]];	//当前的ab边
    		while(area(a,b,p[stk[j]]) < area(a,b,p[stk[j+1]]))	//while循环，找到对踵点j，这里用的是上面说的面积法
    			j = (j+1) % top;	//j一直加1，要对top取余
    		ans = max(ans,max(lens(a,p[stk[j]]),lens(b,p[stk[j]])));	//更新ans，求对踵点的最大值
    	}
    	return ans;	//返回答案
    }
    
    int main()
    { 
    	cin >> n;	//输入n个点
    	for(int i = 0;i < n;i++)
    		cin >> p[i].x >> p[i].y;	//输入点坐标
    	
    	andrew();	//求凸包
    	cout << rotating() << endl;	//旋转卡壳
    
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_45735851/article/details/114553142
[eg]: /images/20221022/c9d737c8ecfa4227b5e37280e52d500f.png
[eg 1]: /images/20221022/1a5f34271208472a8bc2125b3dec5e73.png