【模板】旋转卡壳

link

模板一个。其实感觉说是求凸包的直径倒不如说是求平面内最远点对，毕竟它的输入没保证是个凸包，自己还要再求一遍啊……

旋转卡壳的思想十分优雅易懂，就是先证明平面内最近点对一定是凸包上两点，再根据这个结论，枚举每一条边的同时找出离线段最远的点并更新答案即可。为了尽可能地降低找点的复杂度，对问题进行分析。容易发现距离是单峰的，所以可以用三分查找来做；但事实上没有必要，因为会发现按顺序枚举边的过程中决策点是单调不降的，所以可以直接用高级决策单调性来解决。算法复杂度的瓶颈是凸包部分的排序，故复杂度为 \(O(NlogN)\) 。

有一些小bug。有可能凸包上只有两个点，这就会导致永远都找不到离线段最远的点而死循环，特判即可。另外凸包的边上不应该有点，否则会造成一些错误。

#include
#include
//#define zczc
using namespace std;
const int N=50010;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline int max(int s1,int s2){
	return s11&&!check(st[top-1],st[top],st[top],a[i]))top--;st[++top]=a[i];
	}
	for(int i=1;i1&&!check(st[top],a[i],st[top-1],st[top]))top--;st[++top]=a[i];
	}
	for(int i=top;i>1;i--)s[++cnt]=st[i];
	s[++cnt]=s[1];m=cnt;
	
	if(m<=3){
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++)
				ans=max(ans,dis(s[i],s[j]));
		printf("%d\n",ans);
		return 0;
	}
	
	//求直径
	for(int i=1,last=1;i