#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct point
{
	int x,y;
};
int dist(point a,point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
struct poly{
	point p[70000];
	int n;
	poly(){}
	void init(int nn){n=nn;
		for(int i=0;i<n;++i)
			scanf("%d %d",&p[i].x,&p[i].y);
		p[n]=p[0];return;
	};
};
int mmax(int a,int b)
{
	if(a>b)return a;
	return b;
}
int cross(point a, point b, point c) {
    return (a.x - c.x)*(b.y - c.y)-(a.y - c.y)*(b.x - c.x);
}
int rotating_calipers(poly a)
{
    int q=1,ans=0;
    for(int p=0;p<a.n;p++)
    {
        while(cross(a.p[p+1],a.p[q+1],a.p[p])>cross(a.p[p+1],a.p[q],a.p[p]))
            q=(q+1)%a.n;
        ans=max(ans,max(dist(a.p[p],a.p[q]),dist(a.p[p+1],a.p[q+1])));            
    }
    return ans; 
}
bool operator<(const point &a,const point &b){
	return a.y<b.y||a.y==b.y&&a.x<b.x;
}
void convex(poly a,poly &b){
	b.n=0;
	sort(a.p,a.p+a.n);
	for(int i=0;i<a.n;++i){
		while(b.n>1&&cross(a.p[i],b.p[b.n-2],b.p[b.n-1])<0)--b.n;
		b.p[b.n++]=a.p[i];
	}
	int k=b.n;
	for(int i=a.n-2;i>=0;--i){
		while(b.n>k&&cross(a.p[i],b.p[b.n-2],b.p[b.n-1])<0)--b.n;
		b.p[b.n++]=a.p[i];
	}
	if(b.n>1)--b.n;
		b.p[b.n]=b.p[0];
}
poly a;
int main()
{
	int n,i,j;
	while(scanf("%d",&n)!=EOF)
	{
		a.init(n);
		convex(a,a);
		int ans=rotating_calipers(a);
		printf("%d\n",ans);
	}
	return 0;
}

• Re:跪拜求挑错，谢…… (551) JackyZ 2010-08-26 14:34:15
  • Re:跪拜求挑错，谢…… (2) zhangsiliang880622 2010-08-27 09:13:46