我的代码（TLE）呜呜~~~~(>_<)~~~~ 
#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#define N 50005
using namespace std;
struct point{
	int x,y;
}pt[N];
int convex[N];
int n,k;
int xmult(point a,point b,point c){
	return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
int dist(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)
{
	if(xmult(pt[0],a,b)>0||(xmult(pt[0],a,b)==0&&dist(a,pt[0])<dist(b,pt[0])))return true;
	return false;
}
bool left(int a,int b,int c){
	if(xmult(pt[a],pt[b],pt[c])>=0)return true;
	return false;
}
int max(int a,int b){
	return a>b?a:b;
}
void swap(int a,int b){
	int temp;
	temp=pt[a].x;
	pt[a].x=pt[b].x;
	pt[b].x=temp;

	temp=pt[a].y;
	pt[a].y=pt[b].y;
	pt[b].y=temp;
}
int main()
{
	//freopen("in.txt","r",stdin);
	int t,ans,i,j;
	while(scanf("%d",&n)!=EOF){
		k=t=ans=0;
		for(i=0;i<n;i++){
			scanf("%d %d",&pt[i].x,&pt[i].y);
			if(pt[i].x<pt[k].x)
				k=i;
			else if(pt[i].x==pt[k].x&&pt[i].y<pt[k].y)
				k=i;
		}
		if(k){
			swap(k,0);
		}
		sort(pt+1,pt+n,cmp);
		convex[t++]=0;
		convex[t++]=1;
		convex[t++]=2;
		for(i=3;i<n;){
			if(left(convex[i-2],convex[i-1],i))
				convex[t++]=i++;
			else --t;
		}
		for(i=0;i<t;i++)
			for(j=i+1;j<t;j++)
				ans=max(ans,dist(pt[i],pt[j]));
		printf("%d\n",ans);
	}
	return 0;
}

下面是别人的代码（110ms）：

#include<iostream> 
#include<cmath> 
#include<string> 
#include<algorithm> 
#include<queue> 
#include<cstring> 
#include<cstdio> 
  
using namespace std; 
const double PI=acos(-1); 
const int N=50005; 
struct node 
{ 
    int x,y; 
}mem[N]; 
int used_point[N]; 
int dist(int i,int j)//求两点距离平方 
{ 
    return (mem[i].x-mem[j].x)*(mem[i].x-mem[j].x) 
                +(mem[i].y-mem[j].y)*(mem[i].y-mem[j].y); 
} 
bool cmp(node l1,node l2)//叉积排序 如果相等 近的优先 
{ 
    if((l1.x-mem[0].x)*(l2.y-mem[0].y)==(l2.x-mem[0].x)*(l1.y-mem[0].y)) 
    return ((l1.x-mem[0].x)*(l1.x-mem[0].x)+(l1.y-mem[0].y)*(l1.y-mem[0].y))< 
    ((mem[0].x-l2.x)*(mem[0].x-l2.x)+(mem[0].y-l2.y)*(mem[0].y-l2.y)); 
    return (l1.x-mem[0].x)*(l2.y-mem[0].y)>(l2.x-mem[0].x)*(l1.y-mem[0].y); 
} 
bool Left_turn(int i,int j,int l)//判断是否左转 
{ 
    int x1=mem[j].x-mem[i].x; 
    int y1=mem[j].y-mem[i].y; 
    int x2=mem[l].x-mem[j].x; 
    int y2=mem[l].y-mem[j].y; 
    if(x1*y2>x2*y1)//如果左转 true （这种情况为不要直线上多余的点 如果想要应用 >=) 
    return true; 
    return false; 
} 
int main() 
{ 
    int n; 
    while(scanf("%d",&n)!=EOF) 
    { 
        int k=0; 
        for(int i=0;i<n;++i) 
        { 
            scanf("%d %d",&mem[i].x,&mem[i].y); 
            if(mem[i].y<mem[k].y||(mem[i].y==mem[k].y&&mem[i].x<mem[k].x)) 
            k=i; 
        } 
        if(k!=0) 
        { 
             swap(mem[0].x,mem[k].x); 
             swap(mem[0].y,mem[k].y); 
        } 
        sort(mem+1,mem+n,cmp); 
        int I=0; 
        used_point[I++]=0; 
        used_point[I++]=1; 
        used_point[I++]=2; 
        for(int i=3;i<n;) 
        { 
            if(I<2||Left_turn(used_point[I-2],used_point[I-1],i))//是左转则入栈加一 (I<2)的情况是对于开始就有直线又不要直线上多余点的情况， 
            //防止越界。如果直线上多余的点也要则可不写，但会有多余的点使得效率低 
            used_point[I++]=i++; 
            else//否则出栈 
            --I; 
        } 
        used_point[I]=used_point[0]; 
        int ans=0; 
        for(int i=0;i<I;++i) 
        { 
            for(int j=i+1;j<I;++j) 
            { 
                ans=max(ans,dist(used_point[i],used_point[j]));//枚举最大距离平方 
            } 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
}

• 枚举不是最佳选择， 时间复杂度为O(n^2)； 较好的做法是旋转卡壳 (0) ProgrammingEveryday 2012-09-03 22:06:28