值得一提的是,这是一个“不定向”算法,为什么呢,因为ta的名字不定哈哈哈,旋转卡壳一共有2*3*2*2=24种不同的读音哦
旋转卡壳可以解决:凸多边形最远点对,凸多边形间最远/近点对,最小矩阵覆盖问题
被凸包上被一对平行直线卡住的点对叫对踵点
答案一定出在一对对踵点上
尝试用通过旋转一对平行直线,枚举所有对踵点
按逆时针顺序枚举凸包上一条边,则凸包上到该边所在直线最远的点也单调逆时针旋转,相当于用一条直线卡对面一个顶点
先来看第一个吧:最远点对,可以知道最远点对一定在凸包上
核心操作,那个长长长长的while中的判断是把点到直线的距离变成三角形面积的判断
void rotating() { stack[top+1]=stack[1]; int now=2; for (int i=1;i<=top;i++) { while (dcmp(cj(dian[stack[i+1]]-dian[stack[i]],dian[stack[now]]-dian[stack[i]]) - cj(dian[stack[i+1]]-dian[stack[i]],dian[stack[now+1]]-dian[stack[i]]))<0) now=now%top+1; ans=max(ans,len(dian[stack[now]]-dian[stack[i]])); } }
这个四舍五入的输出技巧值得我们学习。
#include#include #include using namespace std; const double eps=1e-9; int dcmp(double x) { if (x<=eps && x>=-eps) return 0; return (x>0)?1:-1; } struct po { double x,y; po (double X=0,double Y=0){x=X;y=Y;} }dian[50005]; int n,top,stack[50005];double ans; bool operator <(const po &a,const po&b){return a.x 1 && dcmp(cj(dian[stack[top]]-dian[stack[top-1]],dian[i]-dian[stack[top-1]]))<=0) top--; stack[++top]=i; } int k=top; for (int i=n-1;i>=1;i--) { while (top>k && dcmp(cj(dian[stack[top]]-dian[stack[top-1]],dian[i]-dian[stack[top-1]]))<=0) top--; stack[++top]=i; } if (n>1) top--; } double len(po x){return sqrt(x.x*x.x+x.y*x.y);} void rotating() { stack[top+1]=stack[1]; int now=2; for (int i=1;i<=top;i++) { while (dcmp(cj(dian[stack[i+1]]-dian[stack[i]],dian[stack[now]]-dian[stack[i]]) - cj(dian[stack[i+1]]-dian[stack[i]],dian[stack[now+1]]-dian[stack[i]]))<0) now=now%top+1; ans=max(ans,len(dian[stack[now]]-dian[stack[i]])); } } int main() { double x,y; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%lf%lf",&x,&y); dian[i]=po(x,y); } tb(); rotating(); printf("%.0lf\n",ans*ans); }