http://poj.org/problem?id=2187
题目大意：给n个点，求点对最大距离的平方。
————————————————————
很容易证明最大距离的点对在最大凸包上。
那么就是旋转卡壳的裸题了。
旋转卡壳要不要写讲解呢……
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct Point{ int x,y; Point(int x0=0,int y0=0){x=x0,y=y0;} }; int dis(Point a,Point b){//求两点距离平方 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } typedef Point Vector; Vector operator +(Point a,Point b){return Vector(a.x+b.x,a.y+b.y);} Vector operator -(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);} Vector operator *(Point a,int k){return Vector(a.x*k,a.y*k);} Vector operator /(Point a,int k){return Vector(a.x/k,a.y/k);} int Dot(Vector a,Vector b){//求点积 return a.x*b.x+a.y*b.y; } int Cross(Vector a,Vector b){//求叉积 return a.x*b.y-b.x*a.y; } int Cross(Point sp,Point ep,Point op){//得到sp-op和ep-op的叉积 return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y); } Point p[N],q[N]; int n,k,m; inline bool cmp(int u,int v){ int det=Cross(p[u],p[v],p[1]); if(det!=0)return det>0; return dis(p[1],p[u])<dis(p[1],p[v]); } void graham(){ int id=1; for(int i=2;i<=n;i++) if(p[i].x<p[id].x||(p[i].x==p[id].x&&p[i].y<p[id].y)) id=i; if(id!=1)swap(p[1],p[id]); static int per[N]; for(int i=1;i<=n;i++)per[i]=i; sort(per+2,per+n+1,cmp); q[++m]=p[1]; for(int i=2;i<=n;i++){ int j=per[i]; while(m>=2&&Cross(p[j],q[m],q[m-1])>=0)m--; q[++m]=p[j]; } return; } int calliper(){ if(m==2)return dis(q[1],q[2]); q[m+1]=q[1]; int res=0; for(int i=1,j=3;i<=m;i++){ while(Cross(q[i+1],q[j],q[i])<Cross(q[i+1],q[j+1],q[i])){ j++;if(j>m)j=1; } res=max(res,dis(q[i],q[j])); } return res; } int main(){ n=read(); for(int i=1;i<=n;i++)p[i].x=read(),p[i].y=read(); graham(); printf("%d ",calliper()); return 0; }