G - 飞花的传送门
飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。
请你帮他算一算他所挑选的最远的两个传送门有多远。
Input
多组输入。
对于每组输入，第一行输入一个整数N（2 <= N<= 50000），接下来从第2行到第N+1行，每行两个整数（X，Y），代表第i个传送门的坐标（-1000000 <= X, Y<= 1000000）。
数据为随机生成。
Output
输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。
Sample Input
4
0 0
0 1
1 1
1 0
Sample Output
2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct point
{
long long x;
long long y;
} P[],S[]; long long xx;
long long yy; bool cmp(struct point a,struct point b)
{
if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
return a.x<b.x;
} long long CJ(long long x1,long long y1,long long x2,long long y2)
{
return (x1*y2-x2*y1);
} long long Compare(struct point a,struct point b,struct point c)
{
return CJ((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
} long long Dis(struct point a,struct point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
} int main()
{
int n,i,j;
while(~scanf("%d",&n))
{
int top = ;
yy = +;
for(i=;i<n;i++)
{
scanf("%lld%lld",&P[i].x,&P[i].y);
if(P[i].y<yy)
{
yy = P[i].y;
xx = P[i].x;
j = i;
}
}
P[j] = P[];
sort(P+,P+n,cmp);
S[].x = xx;
S[].y = yy;
S[] = P[];
for(i = ;i<n;)
{
if(top&&(Compare(S[top-],S[top],P[i])<)) top--;
else S[++top] = P[i++];
}
long long max1 = -;
for(i = ;i<=top;i++)
for( j = i+;j<=top;j++)
if(Dis(S[i],S[j])>max1)
max1 = Dis(S[i],S[j]);
printf("%lld\n",max1);
}
return ;
}