如果想要知道怎么求凸包的直径
先去学习一下怎么求解凸包
点这里去看凸包
好了
现在知道了凸包是什么
我们很显然可以得出，品面内最远的点对一定在凸包上面（为啥自己想呀）
而凸包的直径也就是凸包上最远点对的距离。
继续，考虑如何求解最远点对
暴力枚举?
显然不一定所有点都会在凸包上，显然比O(n^2)的枚举的效率会更加优秀（但是求解凸包还有一个O(nlogn)）
那么，有没有什么好方法能够求解出最远点对的距离呢？
先来看一个凸包
考虑如何求解距离某一个点最远的点呢？
我们转换一下思路，如果一个点到某一条边的距离最远，那么就可以推出他到这条边的两个端点中的一个一定是最远的。（自己证明，可能我说错了。。。。）
所以，我们依次枚举凸包上的每一条边
计算一下哪个点到他的距离最远，然后计算一下距离
但是，如果就是这样依次枚举的话
时间复杂度依旧是O(n^2)
似乎并没有什么优化
先给凸包标上点
假设我现在考虑的是AB边和他距离最远的点
很显然，D点距离他最远
换条边，换成BC边
这个时候变成了E点
再继续？
看看CD边
这个时候又变成了A点
好了！
我们现在来看看发生了什么
我们的边依次是： AB->BC->CD
而点依次是：D->E->A
发生了一件很神奇的事情
我们的边是逆时针的枚举
而此时距离他们最远的点也是逆时针的出现！！
好了
如果自己分析一下
我们就不难得出
随着边逆时针枚举，
所对应的点也是逆时针出现的
那么，这个时候，利用这个性质，
我们只需要逆时针枚举边，然后从上次枚举到的最远点继续逆时针向后枚举就能求解。
这个时候，O(n^2)被优化到了O(n)
恩，这样求解就会很快了
于是
来转一张动图大致的看一看是怎么弄的
还是细节上的小问题
怎么判断当前的距离是否更大
最直接的方法，用点到直线的距离公式（自己百度）
另外，还有一种方法
我们来看看
对于任意一条边而言
其他的点离他的距离，就是过这个点做平行线到当前的边的距离
而边的长度是固定的，
距离越远，那么，边和点连成的面积也就越大。
还记得上回讲凸包的时候,
我写道：叉积可以用来求面积
那么，这里直接用叉积计算面积即可判断点是否更远。
这就是为啥要单独介绍一下叉积可以用来求解面积。
说到这里差不多了
还是代码（核心）
long long GetMax()//求出直径
{
rg long long re=0;
if(top==1)//仅有两个点
return Dis(S[0],S[1]);
S[++top]=S[0];//把第一个点放到最后
int j=2;
for(int i=0;i<top;++i)//枚举边
{
while(Cross(S[i],S[i+1],S[j])<Cross(S[i],S[i+1],S[j+1]))
j=(j+1)%top;
re=max(re,max(Dis(S[i],S[j]),Dis(S[i+1],S[j])));
}
return re;
}老样子，给你一道模板题
戳我
旋转卡壳的具体实现还是看一看题目吧~
- 还没有人评论，欢迎说说您的想法！
客服
