5 条题解

  • 1
    @ 2026-3-15 11:20:48 
    #include<bits/stdc++.h>
using namespace std;
#define int long long
#define lp tr[p].l
#define rp tr[p].r
#define f(x) ((x)*(x))
const int N=2e5+10,M=2e18;
int w,rt,now,ans;
struct kd
{
	int l,r,z[2],mn[2],mx[2];
	bool operator<(kd a)
	{
		return z[w]<a.z[w];
	}
}tr[N];
void pu(int p)
{
	for(int t=0;t<2;t++)
	{
		tr[p].mn[t]=tr[p].mx[t]=tr[p].z[t];
		if(lp)
		{
			tr[p].mn[t]=min(tr[p].mn[t],tr[lp].mn[t]);
			tr[p].mx[t]=max(tr[p].mx[t],tr[lp].mx[t]);
		}
		if(rp)
		{
			tr[p].mn[t]=min(tr[p].mn[t],tr[rp].mn[t]);
			tr[p].mx[t]=max(tr[p].mx[t],tr[rp].mx[t]);
		}
	}
}
int bt(int l,int r)
{
	if(l>r)return 0;
	int m=(l+r)>>1;w^=1;
	nth_element(tr+l,tr+m,tr+r+1);
	tr[m].l=bt(l,m-1);
	tr[m].r=bt(m+1,r);
	pu(m);return m;
}
int d(int p)
{
	int s=0;
	for(int t=0;t<2;t++)
		s+=f(tr[now].z[t]-tr[p].z[t]);
	return s;
}
int dis(int p)
{
	if(!p)return M;
	int s=0;
	for(int t=0;t<2;t++)
	{
		s+=f(max(tr[now].z[t]-tr[p].mx[t],0ll));
		s+=f(max(tr[p].mn[t]-tr[now].z[t],0ll));
	}
	return s;
}
void qy(int p)
{
	if(!p)return;
	if(p!=now)ans=min(ans,d(p));
	if(dis(lp)<ans)qy(lp);
	if(dis(rp)<ans)qy(rp);
}
signed main()
{
	int n;scanf("%lld",&n);ans=M;
	for(int i=1;i<=n;i++)for(int t=0;t<2;t++)
		scanf("%lld",&tr[i].z[t]);
	rt=bt(1,n);
	for(now=1;now<=n;now++)qy(rt);
	printf("%.4lf\n",sqrt(ans));
	return 0;
}
    • 1
      @ 2026-3-15 9:49:40 
      #include<bits/stdc++.h>
using namespace std;
#define sq(x) ((x)*(x))
#define lc(x) tr[x].l
#define rc(x) tr[x].r
const int N=2e5+10;
int n,K,rt,cur;
double ans=2e18;
struct KD{
	int l,r;
	double v[2];
	double L[2],U[2];
	bool operator < (const KD &A){
		return v[K]<A.v[K];
	}
}tr[N];
void pushup(int p){
	for(int i=0;i<2;i++){
		tr[p].L[i]=tr[p].U[i]=tr[p].v[i];
		if(lc(p)){
			tr[p].L[i]=min(tr[p].L[i],tr[lc(p)].L[i]);
			tr[p].U[i]=max(tr[p].U[i],tr[lc(p)].U[i]);
		}
		if(rc(p)){
			tr[p].L[i]=min(tr[p].L[i],tr[rc(p)].L[i]);
			tr[p].U[i]=max(tr[p].U[i],tr[rc(p)].U[i]);
		}
	}
}
int build(int l,int r){
	if(l>r)return 0;
	int m=(l+r)>>1;
	nth_element(tr+l,tr+m,tr+r+1);
	K^=1;
	lc(m)=build(l,m-1);
	rc(m)=build(m+1,r);
	pushup(m);
	return m;
}
double dis(int p){
	double s=0;
	for(int i=0;i<2;i++)
		s+=sq(tr[cur].v[i]-tr[p].v[i]);
	return s;
}
double dis2(int p){
	if(!p)return 2e18;
	double s=0;
	for(int i=0;i<2;i++)
		s+=sq(max(tr[cur].v[i]-tr[p].U[i],0.0))+sq(max(tr[p].L[i]-tr[cur].v[i],0.0));
	return s;
}
void query(int p){
	if(!p)return;
	if(p!=cur)ans=min(ans,dis(p));
	double dl=dis2(lc(p)),dr=dis2(rc(p));
	if(dl<ans)query(lc(p));
	if(dr<ans)query(rc(p));
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	scanf("%lf%lf",&tr[i].v[0],&tr[i].v[1]);
	rt=build(1,n);
	for(cur=1; cur<=n; cur++) query(rt);
	printf("%.4lf\n",sqrt(ans));
}
      • 0
        @ 2026-3-15 9:45:52

        类董晓的代码:

        #include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,nw,rt,D;double ans=4e18;
struct node
{
	double p[2],mn[2],mx[2];int l,r;
	void pu(node &A)
	{
		for(int i=0;i<2;i++)
			mx[i]=max(mx[i],A.p[i]),mn[i]=min(mn[i],A.p[i]);
	}
}t[N];
double dis(int x)
{
	if(!x)return 4e18;
	double s=0;
	for(int i=0;i<2;i++)
	{
		double u=max(t[nw].p[i]-t[x].mx[i],0.0)
				 +max(t[x].mn[i]-t[nw].p[i],0.0);
		s+=u*u;
	}
	return s;
}
double dis2(int x)
{
	double s=0;
	for(int i=0;i<2;i++)
	{
		double u=t[nw].p[i]-t[x].p[i];
		s+=u*u;
	}
	return s;
}
void query(int x)
{
	if(!x)return ;
	ans=min(ans,dis2(x));
	double lv=dis(t[x].l),rv=dis(t[x].r);
	if(lv<ans)query(t[x].l);
	if(rv<ans)query(t[x].r);
}
void ins(int &x,int d)
{
	if(!x)return void(x=nw);
	ins(t[nw].p[d]<=t[x].p[d]?t[x].l:t[x].r,d^1);
	t[x].pu(t[nw]);
}
int main()
{
	scanf("%d",&n);
	for(int i=0;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);
	for(nw=1;nw<=n;nw++)query(rt),ins(rt,0);
	printf("%.4lf\n",sqrt(ans));
	return 0;
}
        • -1
          @ 2026-3-15 10:36:27

          C19【模板】KD 树 交替建树

          C20【模板】KD 树 插入重构

          #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define lc t[p].l      // 左孩子宏定义
#define rc t[p].r      // 右孩子宏定义
using namespace std;

const int N=200010;     // 最大点数
double ans=2e18;        // 存储当前找到的最小距离的平方
int n,K,root,cur;       // K:当前分割维度, root:根节点, cur:当前查询的点
struct KD{              // KD树节点结构体
  int l,r;              // 左右孩子在数组中的下标
  double v[2];          // 点的坐标值 (v[0]为x坐标, v[1]为y坐标)
  double L[2],U[2];     // 子树区域的坐标范围 L[0]~U[0]为x范围, L[1]~U[1]为y范围
  bool operator<(const KD &b)const{return v[K]<b.v[K];}  // 用于nth_element比较
}t[N];

// 更新节点p的子树范围
void pushup(int p){
  for(int i=0;i<2;i++){                     // i=0处理x坐标, i=1处理y坐标
    t[p].L[i]=t[p].U[i]=t[p].v[i];          // 先初始化为当前点的坐标
    
    if(lc)  // 如果存在左孩子
      t[p].L[i]=min(t[p].L[i],t[lc].L[i]),  // 取左子树的最小值
      t[p].U[i]=max(t[p].U[i],t[lc].U[i]);  // 取左子树的最大值
    
    if(rc)  // 如果存在右孩子
      t[p].L[i]=min(t[p].L[i],t[rc].L[i]),  // 取右子树的最小值
      t[p].U[i]=max(t[p].U[i],t[rc].U[i]);  // 取右子树的最大值
  }
}

// 建树函数: 对区间[l,r]建树, 当前分割维度为k
int build(int l,int r,int k){
  if(l>r) return 0;                         // 空区间返回0
  
  int m=(l+r)>>1;                            // 取中点作为当前节点
  K=k;                                       // 设置全局K为当前分割维度
  nth_element(t+l,t+m,t+r+1);                // 将第m大的数放在m位置,左边小右边大
  
  t[m].l=build(l,m-1,k^1);                   // 递归建左子树,切换维度(0->1,1->0)
  t[m].r=build(m+1,r,k^1);                   // 递归建右子树,切换维度
  
  pushup(m);                                 // 更新当前节点的范围
  return m;                                  // 返回当前节点下标
}

// 平方函数
double sq(double x){return x*x;}

// 计算当前点(cur)到节点p的距离(平方)
double dis(int p){
  double s=0;
  for(int i=0;i<2;i++) 
    s+=sq(t[cur].v[i]-t[p].v[i]);            // 欧氏距离平方
  return s;
}

// 计算当前点(cur)到子树p的最小可能距离(平方)
// 如果点在包围盒内,返回0; 否则返回到包围盒边缘的距离平方
double dis2(int p){
  if(!p) return 2e18;                        // 空节点返回无穷大
  
  double s=0;
  for(int i=0;i<2;++i)
    s+=sq(max(t[cur].v[i]-t[p].U[i],0.0))+   // 当前点x > 最大x, 距离为差值
       sq(max(t[p].L[i]-t[cur].v[i],0.0));   // 当前点x < 最小x, 距离为差值
  return s;                                   // 否则该项距离为0
}

// 查询当前点(cur)的最近邻
void query(int p){
  if(!p) return;
  
  if(p!=cur) ans=min(ans,dis(p));            // 如果不是自己,更新最小距离
  
  double dl=dis2(lc), dr=dis2(rc);            // 计算到左右子树的最小可能距离
  
  // 优先搜索可能距离更小的子树
  if(dl<dr){
    if(dl<ans) query(lc);                     // 左子树可能更近,先搜左
    if(dr<ans) query(rc);                     // 如果右子树也可能有更小距离,再搜右
  }
  else{
    if(dr<ans) query(rc);                     // 右子树可能更近,先搜右
    if(dl<ans) query(lc);                     // 如果左子树也可能有更小距离,再搜左
  }
}

int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
    scanf("%lf%lf",&t[i].v[0],&t[i].v[1]);    // 读入n个点的坐标
  
  root=build(1,n,0);                          // 建树,从x维度开始分割
  
  for(cur=1; cur<=n; cur++)                    // 对每个点查询最近邻
    query(root);
  
  printf("%.4lf\n",sqrt(ans));                 // 输出最小距离(开平方)
}
          • -1
            @ 2026-3-15 9:59:36

            感谢师兄代码（242ms）

            #include<bits/stdc++.h>
using namespace std;
#define lc tr[p].l
#define rc tr[p].r
const int N=2e5+10;
int K,n,rt,cur;
struct node
{
	int l,r;
	double v[2],L[2],U[2];
	bool operator<(const node &b) const {return v[K]<b.v[K];}
}tr[N];
double ans=2e18;
void pushup(int p)
{
	for(int i=0;i<2;i++)
	{
		tr[p].L[i]=tr[p].U[i]=tr[p].v[i];
		if(lc)
		{
			tr[p].L[i]=min(tr[p].L[i],tr[lc].L[i]);
			tr[p].U[i]=max(tr[p].U[i],tr[lc].U[i]);
		}
		if(rc)
		{
			tr[p].L[i]=min(tr[p].L[i],tr[rc].L[i]);
			tr[p].U[i]=max(tr[p].U[i],tr[rc].U[i]);
		}
	}
}
int build(int l,int r,int k)
{
	if(l>r)return 0;
	int m=(l+r)/2;
	K=k;nth_element(tr+l,tr+m,tr+r+1);
	tr[m].l=build(l,m-1,k^1);
	tr[m].r=build(m+1,r,k^1);
	pushup(m);
	return m;
}
double sq(double x){return x*x;}
double dis(int p)
{
	double s=0;
	for(int i=0;i<2;i++)s+=sq(tr[cur].v[i]-tr[p].v[i]);
	return s;
}
double dis2(int p)
{
	if(!p)return 2e18;
	double s=0;
	for(int i=0;i<2;i++)s+=sq(max(tr[cur].v[i]-tr[p].U[i],0.0))+sq(max(tr[p].L[i]-tr[cur].v[i],0.0));
	return s;
}
void q(int p)
{
	if(!p)return;
	if(p!=cur)ans=min(ans,dis(p));
	double d1=dis2(lc),d2=dis2(rc);
	if(d1<d2)
	{
		if(d1<ans)q(lc);
		if(d2<ans)q(rc);
	}
	else
	{
		if(d2<ans)q(rc);
		if(d1<ans)q(lc);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&tr[i].v[0],&tr[i].v[1]);
	rt=build(1,n,0);
	for(int i=1;i<=n;i++)cur=i,q(rt);
	printf("%.4lf\n",sqrt(ans));
	return 0;
}
            • 1

            C19C20【KD 树】平面最近点对（加强版）

            信息

            ID
            329
            时间
            1000ms
            内存
            256MiB
            难度
            8
            标签
            递交数
            193
            已通过
            35
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 10ms
            4. Powered by Hydro v5.0.1 Community