管理备注：虽然此题解为乱搞，但是本乱搞是非常有意义的经典乱搞，故保留在题解区中供学习与参考。
我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 \(x\) 坐标排序。
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太近。
所以排序后把前 \(20000\) 个点和后 \(20000\) 个点暴力枚举更新答案。
这样开 o2 就可以过了。
可以想一想这样乱搞为什么能过？
假设不旋转，出题人会使用一组 \(x\) 轴坐标特别远，\(y\) 轴坐标特别近的数据来卡你。
但是旋转后 \(x\) 轴坐标和 \(y\) 轴坐标的差会变小。
所以就可以通过数据。
此外还有其他的排序方法。
比如将 \(x\) 轴坐标与 \(y\) 轴坐标的乘积作为排序关键字。
原理都是让坐标分布更均匀。
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int maxn=4e5+5;
struct node{
int x,y,lx,ly;
}p[maxn];
bool cmp(node A,node B){
if(A.x<B.x||(A.x==B.x&&A.y<B.y))
return 1;
else
return 0;
}
int dis(node A,node B){
return (A.lx-B.lx)*(A.lx-B.lx)+(A.ly-B.ly)*(A.ly-B.ly);
}
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int X,Y;
cin>>X>>Y;
p[i].lx=X;
p[i].ly=Y;
p[i].x=X*cos(1.14)-Y*sin(1.14);
p[i].y=X*sin(1.14)+Y*cos(1.14);
}
sort(p+1,p+n+1,cmp);
int ans=0;
for(int i=1;i<=min(20000,n);i++){
for(int j=n-min(20000,n)+1;j<=n;j++){
ans=max(ans,dis(p[i],p[j]));
}
}
cout<<ans<<'\n';
}