加入了随机数的思想：

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int maxn=4e5+10;
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,ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	mt19937 Rand(time(0));
    cin>>n;
    int X,Y;
    for(int i=1;i<=n;i++){
        cin>>X>>Y;
        p[i].lx=X;
        p[i].ly=Y;
    }
    for(int i=1;i<=10;i++){
    	double t=(Rand()%99+1.0)/100.0+1.0;
    	for(int i=1;i<=n;i++){
    	    p[i].x=p[i].lx*cos(t)-p[i].ly*sin(t);
    	    p[i].y=p[i].lx*sin(t)+p[i].ly*cos(t);
    	}
    	sort(p+1,p+n+1,cmp);
    	for(int i=1;i<=min(1000,n);i++)
    	    for(int j=n-min(1000,n)+1;j<=n;j++)
    	        ans=max(ans,dis(p[i],p[j]));
	}
    cout<<ans<<'\n';
    return 0;
}

实测可以快很多,而且不容易被卡。

整活