旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。深度学习旋转卡壳请点击这里。
- #include <iostream>
- #include <algorithm>
- #include <stdio.h>
- using namespace std;
- const int N=50005;
- class Point
- {
- public:
- int x;
- int y;
- bool operator < (const Point &P) const
- {
- return y<P.y||(y==P.y&&x<P.x);
- }
- };
- Point stack[N];
- Point p[N];
- int len;
- int dist(Point A,Point B)
- {
- return ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
- }
- int cross(Point A,Point B,Point C)
- {
- return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
- }
- void Graham(int n)
- {
- sort(p,p+n);
- stack[0]=p[0];
- stack[1]=p[1];
- int top=1;
- for(int i=2;i<n;i++)
- {
- while(top>0 && cross(stack[top-1],stack[top],p[i])<=0) top--;
- stack[++top]=p[i];
- }
- int temp=top;
- for(int i=n-2;i>=0;i--)
- {
- while(top>temp && cross(stack[top-1],stack[top],p[i])<=0) top--;
- stack[++top]=p[i];
- }
- len=top;
- }
- int rotating_calipers(int n)
- {
- int k=1,ans=0,i;
- stack[n]=stack[0];
- for(i=0;i<n;i++)
- {
- while(cross(stack[i],stack[i+1],stack[k+1])>cross(stack[i],stack[i+1],stack[k]))
- k=(k+1)%n;
- ans=max(ans,max(dist(stack[i],stack[k]),dist(stack[i+1],stack[k+1])));
- }
- return ans;
- }
- int main()
- {
- int n,i;
- while(~scanf("%d",&n))
- {
- for(i=0;i<n;i++)
- scanf("%d%d",&p[i].x,&p[i].y);
- len=0;
- Graham(n);
- printf("%d\n",rotating_calipers(len));
- }
- return 0;
- }