zcmimi's blog
查看原题

点击跳转

首先: 构建KDT

对每个点分别进行查询,也就是搜索

直接对KDT进行遍历每次搜索的复杂度是O(n)的,显然TLE

这时我们需要估价函数,在这里也就是:

估算出查询点到子树对应的长方形中的点的"最近距离"

若"最近距离"已经超过了当前答案,就跳过当前子树.

搜索时比较左右子树的"最近距离",先搜索"最近距离"小的

#include<bits/stdc++.h>
typedef double db;
#define fur(i,x,y) for(int i(x);i<=y;++i)
const int N=200011,inf=2122219134;
int n,id,ls[N],rs[N];
db ans=2e18,L[N],R[N],D[N],U[N];
struct node{db x,y;}t[N];
bool cmpx(node p,node q){return p.x<q.x;}
bool cmpy(node p,node q){return p.y<q.y;}
db min(db x,db y){return x<y?x:y;}
db max(db x,db y){return x>y?x:y;}
void upd(int x,int y){
    L[x]=min(L[x],L[y]),R[x]=max(R[x],R[y]),
    D[x]=min(D[x],D[y]),U[x]=max(U[x],U[y]);
}
void pu(int x){
    L[x]=R[x]=t[x].x;
    D[x]=U[x]=t[x].y;
    if(ls[x])upd(x,ls[x]);
    if(rs[x])upd(x,rs[x]);
}
int build(int l,int r){
    if(l>r)return 0;
    int m=l+r>>1;
    db ax=0,ay=0,vx=0,vy=0;
    fur(i,l,r)ax+=t[i].x,ay+=t[i].y;
    ax/=(db)(r-l+1),ay/=(db)(r-l+1);
    fur(i,l,r)
        vx+=(ax-t[i].x)*(ax-t[i].x),
        vy+=(ay-t[i].y)*(ay-t[i].y);
    std::nth_element(t+l,t+m,t+r+1,vx>vy?cmpx:cmpy);
    ls[m]=build(l,m-1),rs[m]=build(m+1,r),pu(m);
    return m;
}
db dis(int p){return (t[p].x-t[id].x)*(t[p].x-t[id].x)+(t[p].y-t[id].y)*(t[p].y-t[id].y);}
db f(int p){
    db res=0;
    if(L[p]>t[id].x)res+=(L[p]-t[id].x)*(L[p]-t[id].x);
    if(R[p]<t[id].x)res+=(t[id].x-R[p])*(t[id].x-R[p]);
    if(D[p]>t[id].y)res+=(D[p]-t[id].y)*(D[p]-t[id].y);
    if(U[p]<t[id].y)res+=(t[id].y-U[p])*(t[id].y-U[p]);
    return res;
}
void qry(int l,int r){
    if(l>r)return;
    int m=l+r>>1;
    if(m!=id)ans=min(ans,dis(m));
    if(l==r)return;
    db ld=f(ls[m]),rd=f(rs[m]);
    if(ld<rd){
        if(ld<ans)qry(l,m-1);
        if(rd<ans)qry(m+1,r);
    }
    else{
        if(rd<ans)qry(m+1,r);
        if(ld<ans)qry(l,m-1);
    }
}
int main(){
    scanf("%d",&n);
    fur(i,1,n)scanf("%lf%lf",&t[i].x,&t[i].y);
    build(1,n);
    fur(i,1,n)id=i,qry(1,n);
    printf("%.4f\n",sqrt(ans));
}
LG 1429 平面最近点对(加强版)
comment评论
Search
search