lg保留节目人类智慧

我们充分发扬人类智慧：

将所有点全部绕原点旋转同一个角度，然后按 $x\times x+ y\times y$ 排序。

根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太近。

所以我们只取最远点以及向前的 $4$ 个点来计算答案。

这样速度快得飞起，在 $n=50000$ 时都可以在90ms内卡过，hack数据都起不到效果。

当然我这种蒟蒻肯定是不懂dalao们的想法即使写出能够通过样例的最后只能拿到91pts

#include <bits/stdc++.h>
using namespace std;
const int _ = 4e5+3;
struct Node{
    int x,y,lx,ly;
}p[_];
inline bool cmp(Node a,Node b){
    if((a.x<b.x)||(a.x>b.x&&a.y==b.y))return 1;
    else return 0;
}
inline 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.tie(0)->sync_with_stdio(0);
    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(n+4,n);i++){
        for(int j=n-min(n+4,n)+1;j<=n;j++){
            ans=max(ans,dis(p[i],p[j]));
        }
    }
    cout<<ans<<'\n';
}

所以我们索性直接换一组枚举数量。

#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';
}