Beauty Contest

题目分析：

题目要找图像上两点最长的距离，那么最长的边的两个顶点肯定在凸包上；
先用Graham扫描法求个凸包，在用旋转卡壳求最长边；
注意处理凸包只有一个点和一条线的情况

Code：

#include <bits/stdc++.h>
using namespace std;
#define maxn 50010
#define ll long long

int n,tot;
struct node {
	int x,y;
}e[maxn],P[maxn];

inline double len_(node A,node B) {
	return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );
}

inline double X_(node A,node B,node C) {
	double X1=B.x-A.x;
	double Y1=B.y-A.y;
	double X2=C.x-A.x;
	double Y2=C.y-A.y;
	return ( (X1*Y2) - (X2*Y1) );
}

inline ll lenpf_(node A,node B,node C) {
	ll pd1=( (C.x-A.x)*(C.x-A.x) + (C.y-A.y)*(C.y-A.y) );
	ll pd2=( (C.x-B.x)*(C.x-B.x) + (C.y-B.y)*(C.y-B.y) );
	if(pd1>pd2) return pd1;
	else return pd2;
}

inline bool cmp_(node A,node B) {
	double pd=X_(e[0],A,B);
	if(pd>0) return true;
	if(pd<0) return false;
	return len_(e[0],A)<len_(e[0],B);
}

inline void init_() {
	freopen("BeautyContest.txt","r",stdin);
}

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

inline void readda_() {
	n=read_();
	for(int i=0;i<n;i++) {
		e[i].x=read_();
		e[i].y=read_();
		if(e[i].y<e[0].y) swap(e[i],e[0]);
		else if(e[i].y==e[0].y&&e[i].x<e[0].x) swap(e[i],e[0]); 
	}
}

inline void work_() {
	sort(e+1,e+n,cmp_);
	P[0]=e[0];P[1]=e[1];
	tot=1;
	for(int i=2;i<n;i++) {
		while(tot&&X_(P[tot-1],P[tot],e[i])<=0) --tot;
		++tot;
		P[tot]=e[i];
	}
	
	if(tot==0) {
		printf("0");
		exit(0);
	}
	else if(tot==1) {
		ll ansp=(P[0].x-P[1].x)*(P[0].x-P[1].x) + (P[0].y-P[1].y)*(P[0].y-P[1].y);
		printf("%lld",ansp);
		exit(0);
	}
	int j=2;
	ll ans=0;
	for(int i=0;i<tot;i++) {
		while(X_(P[i],P[i+1],P[j])<X_(P[i],P[i+1],P[(j+1)%(tot+1)])) {
			j=(j+1)%(tot+1);
		}
		ll tpp=lenpf_(P[i],P[i+1],P[j]);
		if(ans<tpp) ans=tpp;
	}
	
	printf("%lld",ans);
}

int main() {
	init_();
	readda_();
	work_();
	return 0;
}