- 求平面最远点对,先求出凸包,再找凸包的直径.
- 使用旋转卡壳,直径一定出现在对踵点对间.比较不同点到同一直线距离可以用叉积算三角形面积来比较.
- 实现时注意关于栈的 (top) 的细节.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=5e4+10;
const double eps=1e-9;
struct v2{
ll x,y;
v2(ll x=0,ll y=0):x(x),y(y) {}
v2 operator + (const v2 &rhs) const
{
return v2(x+rhs.x,y+rhs.y);
}
v2 operator / (const double &rhs) const
{
return v2(x/rhs,y/rhs);
}
v2 operator - (const v2 &rhs) const
{
return v2(x-rhs.x,y-rhs.y);
}
ll operator * (const v2 &rhs) const
{
return x*rhs.y-y*rhs.x;
}
ll modulus2()
{
return x*x+y*y;
}
bool operator < (const v2 &rhs) const
{
return x==rhs.x?y<rhs.y:x<rhs.x;
}
};
v2 origin;
bool cmp(const v2 &a,const v2 &b)
{
double A=atan2(a.y-origin.y,a.x-origin.x),B=atan2(b.y-origin.y,b.x-origin.x);
return A==B?a.x<b.x:A<B;
}
v2 stk[MAXN];
int tp;
void ConvexHull(v2 *p,int n)
{
for(int i=2;i<=n;++i)
if(p[i]<p[1])
swap(p[i],p[1]);//p1为左下角的点
origin=p[1];
sort(p+2,p+n+1,cmp);
stk[tp]=p[1];//从0开始存
for(int i=2;i<=n;++i)
{
while(tp>=2 && (stk[tp]-stk[tp-1])*(p[i]-stk[tp])<=0)
--tp;
stk[++tp]=p[i];
}
}
ll RotatingCaliper()
{
if(tp==1)
return (stk[0]-stk[1]).modulus2();
stk[++tp]=stk[0];
ll ans=0;
int j=2;
for(int i=0;i<tp;++i)
{
while(abs((stk[i]-stk[j])*(stk[i+1]-stk[j]))<abs((stk[i]-stk[j+1])*(stk[i+1]-stk[j+1])))
j=(j+1)%tp;
ans=max(ans,(stk[i]-stk[j]).modulus2());
ans=max(ans,(stk[i+1]-stk[j]).modulus2());
}
return ans;
}
int n;
v2 p[MAXN];
int main()
{
// freopen("testdata.in","r",stdin);
n=read();
for(int i=1;i<=n;++i)
scanf("%lld%lld",&p[i].x,&p[i].y);
ConvexHull(p,n);
ll ans=RotatingCaliper();
printf("%lld
",ans);
return 0;
}
//785190749
