测试地址：Beauty Contest
题目大意：平面上有N（N≤50000）个点，输出这些点之间最大的距离的平方。
做法：这道题需要用到旋转卡壳。
我们很容易想到枚举所有点对，然后求距离最大值，然而这是O(N^2)的，对于这一题是不行的，那么怎么办呢？
有一个显而易见的结论：平面上最远点对一定在它们的凸包上。我们可以求出凸包，然后对于凸包上的顶点枚举，然而凸包上的点也有可能达到50000个，这时候就要用到旋转卡壳了。旋转卡壳的模板我是按这个的思想写的。这时候又有一个显而易见的结论：平面上最远点对一定是对踵点对，而对踵点对的数量可以证明是不超过3N/2的，这就保证了算法的复杂度为O(N)，结合求凸包的O(NlogN)，总时间复杂度为O(NlogN)，可以通过全部数据（而且很快）。
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 1000000000
using namespace std;
int n,s[50010],t,next[50010],ans;
struct point
{
int x,y;
point operator - (point a) const
{
point s;
s.x=x-a.x;
s.y=y-a.y;
return s;
}
}p[50010];
int dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int multi(point a,point b)
{
return a.x*b.y-b.x*a.y;
}
bool cmp(point a,point b)
{
int s=multi(a-p[1],b-p[1]);
if (s!=0) return s>0;
else return dis(p[1],a)<dis(p[1],b);
}
void graham_scan()
{
int lx=inf,ly=inf,li;
for(int i=1;i<=n;i++)
{
if (p[i].x<lx||(p[i].x==lx&&p[i].y<ly))
{
lx=p[i].x;
ly=p[i].y;
li=i;
}
}
swap(p[1],p[li]);
sort(p+2,p+n+1,cmp);
s[1]=1;t=1;
for(int i=2;i<=n;i++)
{
while(t>1&&multi(p[i]-p[s[t-1]],p[s[t]]-p[s[t-1]])>=0) t--;
s[++t]=i;
}
}
void rotating_calipers()
{
int ly,li,lj,i,j;
ly=inf;for(int i=1;i<=t;i++) if (p[s[i]].y<ly) ly=p[s[i]].y,li=i;
ly=-inf;for(int i=t;i>=1;i--) if (p[s[i]].y>ly) ly=p[s[i]].y,lj=i;
i=s[li],j=s[lj];
for(int i=1;i<t;i++) next[s[i]]=s[i+1];
next[s[t]]=s[1];
do
{
while(multi(p[i]-p[j],p[next[i]]-p[j])<multi(p[i]-p[next[j]],p[next[i]]-p[next[j]])) j=next[j];
ans=max(ans,dis(p[i],p[j])),ans=max(ans,dis(p[next[i]],p[j]));
ans=max(ans,dis(p[i],p[next[j]])),ans=max(ans,dis(p[next[i]],p[next[j]]));
i=next[i];
}while(i!=s[li]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
if (n>2)
{
ans=0;
graham_scan();
rotating_calipers();
printf("%d",ans);
}
else printf("%d",dis(p[1],p[2]));
return 0;
}