#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100000+10;

int N,top;

struct node{
	int x,y;
}p[maxn],point,stack[maxn];

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int get_cross(node a,node b,node c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int get_dis(node a,node b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

void find_point(){
	int col=0; point=p[0];
	for(int i=1;i<N;i++){
		if(p[i].y<point.y || (p[i].y==point.y && p[i].x<point.x)){
			col=i; point=p[i];
		}
	}
	swap(p[0],p[col]);
}

bool cmp(node a,node b){//we sort these points as the clockwise.
	int t=get_cross(point,a,b);
	if(t<0)return true;
	if(t>0)return false;
	int xx=get_dis(point,a),yy=get_dis(point,b);
	return xx<yy;
}

void Graham(){
	top=1; p[N]=p[0];
	stack[0]=p[0]; stack[1]=p[1];
	for(int i=2;i<=N;i++){//it rotates as the clockwise.
		while(top>=1 && get_cross(stack[top-1],stack[top],p[i])>=0)top--;
		stack[++top]=p[i];
	}
}

void rotating_colipers(){
	int ans=0,x=2; stack[top+1]=stack[0];
	for(int i=1;i<=top;i++){
		while(get_cross(stack[x+1],stack[i+1],stack[i])>get_cross(stack[x],stack[i+1],stack[i])){
			x=(x+1)%top;
		}
		ans=max(ans,get_dis(stack[x],stack[i]));
		ans=max(ans,get_dis(stack[x+1],stack[i+1]));
	}
	printf("%d",ans);
}
int main(){
	N=read();
	for(int i=0;i<N;i++){
		p[i].x=read(); p[i].y=read();
	}
	if(N==2)printf("%d",get_dis(p[0],p[1]));
	else{
		find_point();
		sort(p+1,p+N,cmp);
		Graham();
		rotating_colipers();
	}
	return 0;
}

• 我只能说数据里有在一条直线上的情况。。。 (34) SaiDLuffy 2015-03-17 17:47:00
• 已AC (1871) porker2008 2015-03-17 17:55:54