题意:
题目链接
给定 \(n\) 个点,求距离最远的两个点之间的距离,输出最远距离的平方 \(n<=50000\)
思路:
旋转卡壳。。。
注意事项:
数组名称不要弄混了
code:
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
int n,top,per[N],res;
struct point{int x,y;int dist(){return x*x+y*y;}}p[N],q[N];
point operator-(point x,point y){return (point){x.x-y.x,x.y-y.y};}
int operator^(point x,point y){return x.x*y.y-x.y*y.x;}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')w=-1;
for(;'0'<=ch&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline bool cmp(int x,int y)
{
int dit=(p[x]-p[1])^(p[y]-p[1]);
if(dit)return dit>0;
return (p[x]-p[1]).dist()<(p[y]-p[1]).dist();
}
inline void Graham()
{
for(int i=2;i<=n;++i)
if(p[1].x>p[i].x||(p[1].x==p[i].x&&p[1].y>p[i].y))
swap(p[1],p[i]);
for(int i=1;i<=n;++i)per[i]=i;
sort(per+2,per+n+1,cmp);
q[++top]=p[1];
for(int i=2;i<=n;++i)
{
int j=per[i];
while(top>1&&((p[j]-q[top-1])^(q[top]-q[top-1]))>=0)--top;
q[++top]=p[j];
}
q[top+1]=q[1];
}
inline int nxt(int x){return x==top?1:x+1;}
inline int S(point x,point y){return abs(x^y);}
inline int solve()
{
if(top==2) return (q[1]-q[2]).dist();
for(int i=1,j=3;i<=top;++i)
{
while(i!=nxt(j)&&S(q[i]-q[j],q[i+1]-q[j])<=S(q[i]-q[j+1],q[i+1]-q[j+1]))
j=nxt(j);
res=max(res,(q[i]-q[j]).dist());
res=max(res,(q[i+1]-q[j]).dist());
}
return res;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
scanf("%d%d",&p[i].x,&p[i].y);
Graham();
printf("%d\n",solve());
return 0;
}