学步园

第一次写旋转卡壳，所以对旋转卡壳部分做了较详细的注释。

如果，知道了旋转卡壳的想法，而不太清楚如何实现的话，欢迎参考。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef struct{int x,y;} Dot;
Dot KEY;
Dot operator -(Dot a,Dot b){Dot c={a.x-b.x,a.y-b.y};return c;}//向量减法
int operator *(Dot a,Dot b){return a.x*b.y-b.x*a.y;}//叉乘
int pow(int a){return a*a;}
int dis2(Dot a,Dot b){return pow(a.x-b.x)+pow(a.y-b.y);}
bool cmp(Dot a,Dot b){return a.x!=b.x?a.x<b.x:a.y<b.y;}//找极点
bool cmp1(Dot a,Dot b)//极角排序
{
	int t;
	t=(a-KEY)*(b-KEY);
	return t!=0?t>0:dis2(a,KEY)<dis2(b,KEY);
}
void show(Dot *box,int top)//旋转卡壳
{
	Dot t;
	int tt,ymin=0,ymax=0,i,n=top+1,ans=0;
	for(i=0;i<n;i++)//找两个端点，一个y最大，一个y最小
	{
		if(box[i].y<box[ymin].y)
			ymin=i;
		if(box[i].y>box[ymax].y)
			ymax=i;
	}
	box[n]=box[0];//因为要用到循环队列，把第n个元素赋值为首地址的元素
	for(i=0;i<n;i++)//遍历凸包顶点，找到每个顶点的对踵点
	{
		t=box[ymin+1]-box[ymin];
		while(t*(box[ymax]-box[ymin])<t*(box[ymax+1]-box[ymin]))
			ymax=(ymax+1)%n;
		//找到后，求它们之间的距离,并更新最大距离ans。
		//由于一个端点直接与逆时针的下一个相邻顶点的方向构成一条射线，所以也就是求
		//另一个端点与这条射线上的两个顶点的最大距离
		ans=max(ans,max(dis2(box[ymin],box[ymax]),dis2(box[ymin+1],box[ymax])));
		ymin=(ymin+1)%n;
	}
	printf("%d\n",ans);
}
int main()
{
	int i,n,top,j;
	Dot dot[50010],box[50010];
	cin>>n;
	for(i=0;i<n;i++)
		cin>>dot[i].x>>dot[i].y;
	sort (dot,dot+n,cmp);
	KEY=dot[0];
	sort (dot+1,dot+n,cmp1);
	box[0]=dot[0];box[1]=dot[1];top=1;
	for(i=2;i<n;)
	{
		if((box[top]-box[top-1])*(dot[i]-box[top-1])>=0)
			box[++top]=dot[i++];
		else
			top--;
	}
	show(box,top);
}