#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=50005;
struct point
{
   double x,y;     
};
point points[MAX],res[MAX];

bool mult(const point sp,const point ep,const point op)
{
    return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);     
}

bool operator < (const point &l, const point r)
{
     return l.y<r.y||(l.y==r.y&&l.x<r.x);
}

double dis(point a, point b)
{
       return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int graham(point pnt[], int n, point res[])
{
    int i,len,k=0,top=1;
    sort(pnt, pnt+n );
    if(n==0)return 0; res[0]=pnt[0];
    if(n==1)return 1; res[1]=pnt[1];
    if(n==2)return 2; res[2]=pnt[2];
    for(i=2; i<n; i++)
    {
             while(top&&mult(pnt[i],res[top],res[top-1]))
                 top--;
             res[++top]=pnt[i];
    }
    len=top;  res[++top]=pnt[n-2];
    for(i=n-3; i>=0; i--)
    {
               while(top!=len&&mult(pnt[i],res[top],res[top-1]))
               top--;
               res[++top]=pnt[i];
    }
    return top;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
            cin>>points[i].x>>points[i].y;
    
    int top=graham(points, n, res);
    double ans=0;
    
    for(int i=0; i<top; i++)
    for(int j=i+1; j<top; j++)
            if(dis(res[i],res[j])>ans)ans=dis(res[i],res[j]);
    cout<<int(ans+0.0005)<<endl;
    system("pause");
    return 0;
}

• Orz...使用模板，过题神速 (1598) smwwh 2010-09-04 21:51:13
• Re:我承认，我抄的模板（吉林大学的） 最短距离枚举凸包的顶点 (67) zzsx65zdf 2011-12-03 21:05:50