题解 P1429 【平面最近点对（加强版）】

· · 题解

蒟蒻不会写分治,只好用K-Dtree骗分...

既然用K-Dtree, 就不需要什么思考了

直接一个一个点在树里找和它距离最小的点, 找完了插进去就行了

K-Dtree找一次的复杂度据说是O(\sqrt n)的, 所以就可以过

还有一种用K-Dtree的写法是不插点, 而是先建好树, 直接把点丢进去找

但是对于这种写法, 找的时候如果找到相同的点要忽略

还是觉得前一种写法比较优

下面是代码

#include<bits/stdc++.h>
using namespace std;
int n,nw,rt,D; double ans=4e18;
struct Node {
  double p[2],mn[2],mx[2]; int l,r; //p:点   mn,mx:子树区域坐标极值  l,r:    孩子
  void up(Node &A) {
    for (int i=0;i<2;++i)
      mn[i]=min(mn[i],A.p[i]),mx[i]=max(mx[i],A.p[i]);
  }
} t[50005];
double get(int u) { //当前点nw到u的子树区域的最小可能距离
  if (!u) return 4e18; double s=0;
  for (int i=0;i<2;++i) {
    double x=max(t[nw].p[i]-t[u].mx[i],0.0)
        +max(t[u].mn[i]-t[nw].p[i],0.0);
    s+=x*x;
  }
  return s;
}
double dis(int u) { //当前点nw到点u的距离
  double s=0;
  for (int i=0;i<2;++i) {
    double x=t[nw].p[i]-t[u].p[i];
    s+=x*x;
  }
  return s;
}
void Query(int u) { //K-Dtree的询问
  if (!u) return; ans=min(ans,dis(u));
  double lv=get(t[u].l),rv=get(t[u].r);
  if (lv>rv) {
    if (rv<ans) Query(t[u].r); if (lv<ans) Query(t[u].l);
  }
  else {
    if (lv<ans) Query(t[u].l); if (rv<ans) Query(t[u].r);
  }
}
void Ins(int &u,int d) {    //二叉查找树式的插点
  if (!u) return void(u=nw);
  Ins(t[nw].p[d]<=t[u].p[d] ? t[u].l : t[u].r,d^1);
  t[u].up(t[nw]);
}
int main() {
  scanf("%d",&n);
  for (int i=1;i<=n;++i) {
    scanf("%lf%lf",&t[i].p[0],&t[i].p[1]);
    for (int j=0;j<2;++j) t[i].mn[j]=t[i].mx[j]=t[i].p[j];
  }
  random_shuffle(t+1,t+n+1);    //我好懒啊不想写重构就rand一下顺序吧反正结果一样
  for (nw=1;nw<=n;++nw) Query(rt),Ins(rt,0);
  printf("%.2lf\n",sqrt(ans));
}