#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define Max 50001

struct Point
{	int x,y;};

int sig(int a)
{	if(!a)
		return 0;
	return a>0? 1:-1;
}

Point p[Max];int stack[Max];
int top,n;

int  dis(Point p1,Point p2)
{	int d=(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
	return d;
}

int cross(Point p1,Point p2,Point p3)
{	return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);}

bool comp(Point p1,Point p2)
{	if(p1.y==p2.y)
		return p1.x<p2.x;
	else
		return p1.y<p2.y;
}

void graham()
{	if(n<=1)
	{	top=1;
		return ;
	}
	sort(p+1,p+n+1,comp);
	top=0;
	stack[++top]=1;
	stack[++top]=2;
	for(int i=3;i<=n;i++)
	{	if(top>=2&&sig(cross(p[stack[top-1]],p[i],p[stack[top]]))>=0)top--;
		stack[++top]=i;
	}
	int temptop=top;
	stack[++top]=n-1;
	for(int i=n-2;i>=1;i--)
	{	if(top>=temptop+1&&sig(cross(p[stack[top-1]],p[i],p[stack[top]]))>=0)top--;
		stack[++top]=i;
	}
	int max=-1;
   for(int i=1;i<=top;++i)
    {   for(int j=i;j<=top;++j)
        {  int tem=dis(p[stack[i]],p[stack[j]]);
          if( tem>max )
             max=tem;
        }
    }
   
   printf("%d\n",max);
return ;
}


int main()
{
	while(cin>>n)
	{	for(int i=1;i<=n;i++)
			cin>>p[i].x>>p[i].y;
		graham();
	}
return 0;

}
	

• Re:TLE为什么老是这样啊 (8) zhangsiliang880622 2010-08-24 10:59:54
• Re:TLE为什么老是这样啊 (1275) zhangsiliang880622 2010-08-24 11:09:01