题意：给你一个数据范围在2~5e4范围内的横纵坐标在-1e4~1e4的点，问你任意两点之间的距离的最大值的平方等于多少？
一道卡壳凸包的模板题，也是第一次写计算几何的题，就看了些模板，关于预备知识;我是直接找到左下角的点，排好序之后，就直接形成凸包，之后调用rotating_calipers()求解；里面注意在凸包构造好之后，因为是++top的，所以在后面卡壳里面%top会出现问题，所以循环之后再一次++top;开始看graham()里面的while循环看了很久，其实就是维护一个逆时针旋转单调栈，还有一点就是在卡壳里面的while循环里面，为什么直接对q递增，之后%top;能过证明当三角形面积(叉乘)在增大时，边长也在增大；
本文参考 孟起
// 110ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
const int MAXN = 5e4+;
struct point{
int x,y;
point(){}
point(int _x,int _y){
x = _x; y = _y;
}
int operator *(const point &b)const{
return (x*b.y - y*b.x);
}
point operator -(const point &b)const{
return point(x - b.x,y - b.y);
} void input(){
scanf("%d%d",&x,&y);
}
}p[MAXN];
int dist2(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b) // 正表示逆时针，返回true表示不要交换；
{
int cp = (a-p[])*(b-p[]);
if(cp < ) return false;
if(cp == && (dist2(a,p[]) >= dist2(b,p[])) ) return false;
return true;
} int stk[MAXN],top;
void graham(int n) // 形成凸包；
{
int i;
stk[] = ;stk[] = ;
top = ;
for(i = ;i < n;i++){ // 构造一个逆时针旋转的单调栈；
while(top > && (p[stk[top]] - p[stk[top-]])*(p[i] - p[stk[top-]]) <= )
top--;
stk[++top] = i;
}
stk[++top] = ;//为了下面%top，很容易知道n-1号元素一定在凸包里面；
/*for(i=0;i<n;i++)
printf("**%d %d\n",p[i].x,p[i].y);
printf("\n%d\n",top); // 0 ~ top - 1;
for(i=0;i<top;i++)
printf("**%d %d\n",p[stk[i]].x,p[stk[i]].y);*/
} int rotating_calipers() //卡壳
{
int q = ,ans = ;
stk[top] = ;
for(int i = ;i < top;i++){
point tmp = p[stk[i+]] - p[stk[i]];
while((tmp * (p[stk[q+]] - p[stk[i]])) > (tmp * (p[stk[q]] - p[stk[i]]))) // 叉积与面积和边长的关系；
q = (q+)%top;
ans = max(ans,max(dist2(p[stk[i+]],p[stk[q+]]),dist2(p[stk[i]],p[stk[q]])));//最好的是i&&q,但是有平行的情况，so:max
}
return ans;
}
int main()
{
int i,n;
while(scanf("%d",&n) == ){
for(i = ;i < n;i++)
p[i].input();
int st = ;
for(i = ;i < n;i++) //选出起始点；
if(p[st].y > p[i].y||(p[st].y == p[i].y && p[st].x > p[i].x))
st = i;
swap(p[],p[st]);
sort(p+,p+n,cmp);//以p[0]为参考点逆时针极角由近到远排序；
graham(n);
printf("%d\n",rotating_calipers());
}
return ;
}