P1452 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G
旋转卡壳模板题。凸包用的是Andrew算法，就不详述了，具体可以查查资料了解，但提一嘴Andrew算法的一些细节问题：
Andrew算法的一些细节
Andrew算法的模板代码如下：
sort(a+1,a+1+n,cmp);
st[++top]=1;
for(int i=2;i<=n;i++){
while(top>=2&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
if(vis[i]) continue;
while(top>tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
其中求叉积的部分，\(\ge\)和\(>\)是有区别的。\(\ge\)表示如果方向相同也要删去，结果就不会出现点在凸包边上的情况；\(>\)则是不删，结果就可能出现点在凸包边上的情况。
如果是求周长两种都可以，不过这道题使用\(>\)会很麻烦：考虑所有点都共线，这样最终结果就是所有点都在凸包上，如果不特判，下一步找直径就会出现高度相同导致的死循环（具体见下面的实现细节）。如果特判共线的话，代码又难以实现。
不如仅保留两端的点，这样我们特判条件就是\(n=3\)。
还有就是\(\ge\)和\(\le\)的区别。其实这两种的答案都是对的，只不过一个顺时针一个逆时针而已。
旋转卡壳
一个拥有\(2^4\)种读音的算法
旋转卡壳是用于解决平面最远点对问题的算法。时间复杂度为\(O(n\log n)\)。
首先我们发现，对这些点求一个凸包，最远点对一定在凸包上。而且因为是一个凸多边形，所以每个顶点到某一边的距离一定是先递增再递减的。
（注意每个顶点到某个顶点的距离并不是一定先递增再递减，考虑下图的形状。）
另外我们发现，每条边能连出的最长线段，一定是和它距离最大的顶点和它\(2\)个端点连出线段的其中之一。
所以我们可以枚举每一条边，找出到这条边距离最大的顶点（刚才已经推出距离是先递增再递减的），然后用这条边的\(2\)个端点和该点分别求距离，再更新最大值即可。
但这种做法显然是\(O(n^2)\)的。我们可以用双指针优化，因为这是凸多边形，所以考虑的边顺时针移到下一个，点一定不会逆时针走。所以每次点不需要从头开始走，从上一个位置开始走就行了。时间复杂度\(O(n)\)，再加上求凸包的\(O(n\log n)\)，一共是\(O(n\log n)\)。
需要特判的情况：如果凸包只有两个顶点，
该题的实现细节
实现细节：
- 注意要输出长度的平方。然后如果直接用\(double\)求平方可能会有微小的误差，导致输出出现科学计数法，所以需要取整（显然平方后是整数）。
- 旋转卡壳时，如果距离相同要贪心地继续取，因为相等不意味着取到最大值了。
- 如果求完凸包，栈里有\(3\)个元素（最少就是\(3\)个），那么需要特判，否则距离相同就会不断取下一个，导致死循环。
- 旋转卡壳时，取“\(cur\)的下一个顶点”，可以取模\(top-1\)而非\(top\)，因为最后\(1\)个元素和第\(1\)个元素是相同的。
Code
凸包用Andrew算法实现。
#include<bits/stdc++.h>
#define nxtnode(x) (x%(top-1))+1
using namespace std;
struct vec{
double x,y;
vec operator+(const vec b){return {x+b.x,y+b.y};}
vec operator-(const vec b){return {x-b.x,y-b.y};}
double len(){return sqrt(x*x+y*y);}
}a[50010];
bool cmp(vec a,vec b){
if(a.x<b.x) return 1;
if(a.x>b.x) return 0;
return a.y<b.y;
}
inline double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
int n,st[50010],top;
double ans;
bool vis[50010];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n,cmp);
st[++top]=1;
for(int i=2;i<=n;i++){
while(top>=2&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
if(vis[i]) continue;
while(top>tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
if(top==3) ans=(a[st[2]]-a[st[1]]).len();//特判
else{
int cur=1;
for(int i=1;i<top;i++){
vec bottom=a[st[i+1]]-a[st[i]];
while(fabs(cross(bottom,a[st[nxtnode(cur)]]-a[st[i]]))>=
fabs(cross(bottom,a[st[cur]]-a[st[i]]))){
//这里用叉积的平四面积代替距离，因为底边是一样的，所以距离（高）和面积成正比
cur=nxtnode(cur);
}
ans=max(ans,max((a[st[cur]]-a[st[i]]).len(),(a[st[cur]]-a[st[i+1]]).len()));
}
}
cout<<(int)(ans*ans)<<"\n";
return 0;
}