平面最近点对149pts求助

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

djwj323 @ 2022-05-31 15:34:45

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x,y;
}z[400003];
int n,i;
long long w(node A,node B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
bool cmp(node A,node B){return A.x==B.x?A.y<B.y:A.x<B.x;}
bool cmp_PLUS(int A,int B){return z[A].y<z[B].y;}
long long s(int l,int r){
    if(l==r)  return 1e18;
    if(l==r-1)  return w(z[l],z[r]);
    int mid=(l+r)/2,p[400003],t=0;
    long long ans=min(s(l,mid),s(mid+1,r)),c=sqrt(ans);
    for(int i=l;i<=r;i++)
        if(abs(z[i].x-z[mid].x)<=c)  p[++t]=i;
    sort(p+1,p+t+1,cmp_PLUS);
    for(int i=1;i<=t;i++)
        for(int j=i+1;j<=t&&z[p[j]].y-z[p[i]].y<c;j++)  ans=min(ans,w(z[p[i]],z[p[j]])),c=sqrt(ans);
    return ans;
}
int main(){
    for(scanf("%d",&n),i=1;i<=n;i++)  scanf("%lld%lld",&z[i].x,&z[i].y);
    return sort(z+1,z+n+1,cmp),printf("%lld",s(1,n)),0;
}
//YuKai AK CSP
//YuKai AK NOIP
//YuKai AK NOI
//YuKai AK IOI
//YuKai AK ZJOI2022

by Iwara_qwq @ 2022-05-31 15:40:56

卡精度,当时我答案差1,加上0.1之后取个整就过了


by djwj323 @ 2022-05-31 15:54:53

已过


|