哦,所以这就是所谓的加强加强版?!

P7883 平面最近点对(加强加强版)

STUDENT00 @ 2022-10-28 21:13:14

我用排序 x 过了加强版,现在又用排序 x x + y y 过了加强加强版……

#include<bits/stdc++.h>
using namespace std;
int n;
struct Node{
    int x,y;
} node[400010];
long long mins=1e18;
bool cmp(Node a,Node b){
    return (long long)a.x*a.x+(long long)a.y*a.y<(long long)b.x*b.x+(long long)b.y*b.y;
}
long long disx(int a,int b){
    return (long long)(node[a].x-node[b].x)*(node[a].x-node[b].x);
}
long long disy(int a,int b){
    return (long long)(node[a].y-node[b].y)*(node[a].y-node[b].y);
}
long long dis(int a,int b){
    return disx(a,b)+disy(a,b);
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++) scanf("%d%d",&node[i].x,&node[i].y);
    sort(node+1,node+n+1,cmp);
    for(register int i=1;i<n;i++){
        for(register int j=i+1;j<=i+50&&j<=n;j++) mins=min(mins,dis(i,j));
    }
    printf("%lld",mins);
    return 0;
}

by STUDENT00 @ 2022-10-28 21:15:55

嗯,真棒,现在的提交记录:

https://www.luogu.com.cn/record/91952682


by STUDENT00 @ 2022-10-28 21:16:26

建议搞个加强加强加强版!


by what_can_I_do @ 2022-10-28 21:23:23

@YuRuochen %大佬


by batman0365 @ 2022-10-29 14:05:30

大佬


by LeoDreamer @ 2022-12-08 08:21:39

佩服,建议折磨出题人再出个hack数据(


by Zimo_666 @ 2023-01-31 15:25:40

牛 你真牛!!!!


|