学习笔记：旋转卡壳

参考博客

• 凸包的直径——旋转卡壳（Via.小蒟蒻yyb）

例题

• 洛谷 P1452 Beauty Contest

参考代码

const int MAXN = 50005;
const double EPS = 1E-8;

inline int dcmp(double x)
{
	if (fabs(x) < EPS) return 0;
	else return x > 0 ? 1 : -1;
}

struct Vector
{
	double x,y;
	Vector(double _x = 0,double _y = 0) : x(_x),y(_y) {}
	friend bool operator <(const Vector &VecA,const Vector &VecB)
	{
		if (VecA.x < VecB.x || (VecA.x == VecB.x && VecA.y < VecB.y)) return true;
		else return false;
	}
	
	friend Vector operator -(const Vector &VecA,const Vector &VecB)
	{
		return Vector(VecA.x - VecB.x,VecA.y - VecB.y);
	}
	
	friend double operator ^(const Vector &VecA,const Vector &VecB)
	{
		return VecA.x * VecB.y - VecA.y * VecB.x;
	}
	
	friend double dis(const Vector &VecA,const Vector &VecB)
	{
		return (VecA.x - VecB.x) * (VecA.x - VecB.x) + (VecA.y - VecB.y) * (VecA.y - VecB.y);
	}
}pos[MAXN],Stack[MAXN];

int n,top;
double ans;

void getHull()
{
	for (int i = 0;i <= n - 1;++i)
	{
		while (top >= 2 && dcmp((Stack[top - 1] - Stack[top - 2]) ^ (pos[i] - Stack[top - 1])) <= 0) top--;
		Stack[top++] = pos[i];
	}
	int c = top;
	for (int i = n - 2;i >= 0;--i)
	{
		while (top >= c + 1 && dcmp((Stack[top - 1] - Stack[top - 2]) ^ (pos[i] - Stack[top - 1])) <= 0) top--;
		Stack[top++] = pos[i];
	}
}

void getMax()
{
	int j = 2;//第三个点。因为Stack[]是0基准的。
	for (int i = 0;i <= top - 2;++i)
	{
		while (((Stack[i + 1] - Stack[i]) ^ (Stack[j] - Stack[i + 1])) < ((Stack[i + 1] - Stack[i]) ^ (Stack[j + 1] - Stack[i + 1])))
			j = (j + 1) % (top - 2);
		ans = max(ans,max(dis(Stack[j],Stack[i]),dis(Stack[j],Stack[i + 1])));
	}
	printf("%.0lf",ans);
}

void init()
{
	scanf("%lld",&n);
	for (int i = 0;i <= n - 1;++i) scanf("%lf%lf",&pos[i].x,&pos[i].y);
	sort(pos,pos + n);
}

void work()
{
	getHull();
	getMax();
}

• 关于凸包

我们枚举凸包上所有的边（实际上是两个端点，for (int i = 0;i <= top - 2;++i)），对于每条边，找到凸包上其他的点到这条边的距离最大值。

以边$p_1p_2$p1​p2​为例计算点到直线的距离：

• $d = |\frac{Ax_0 + By_0 + C}{\sqrt{A^2 + B^2}}|$d=∣A2+B2​Ax0​+By0​+C​∣，直线方程为$Ax+By+C=0$Ax+By+C=0，点$P$P的坐标为$(x_0,y_0)$(x0​,y0​)。
• 利用向量叉积，由于平行四边形的一条边（$p_1p_2$p1​p2​）是已知的，可以通过比较$p_1$p1​和$p_4,p_5,p_6...$p4​,p5​,p6​...组成的向量和向量$\overrightarrow{p_1p_2}$p1​p2​​的叉积，来比较它们到当前边的距离。

while ((Stack[i + 1] - Stack[i]) ^ (Stack[j] - Stack[i + 1])) < ((Stack[i + 1] - Stack[i]) ^ (Stack[j + 1] - Stack[i + 1])) 
	j = (j + 1) % (top - 2);//防止溢出。

若有更优，更新即可。

根据top的定义，图中top的值为8，但实际上组成凸包的点一共只有top - 2 = 6个。所以，当j枚举到7时，应对top - 2取模。

若有谬误，敬请斧正。