ACWing 119 袭击 题解

ACWing 119 袭击 题解

题面

给定$2n$个点($1\leq n\leq 10^5$),求前$n$个点与后$n$个点的最近距离.

题解

之前写分治的做法不知为什么总是$TLE\dots$不得不改成了KJ-D Tree才过的……至于为什么写这么愚蠢的一道题,主要是因为这道题写了$\infty$遍,写到自闭了,现在过了,就当做K-D Tree的模板庆祝一下吧.

由于本题分了类,因此我们的K-D Tree不需要动态加点了,也甭按照谁的方差大来算了,直接前$n$个点random_shuffle然后按照深度轮流以$x$,$y$为划分的标准就可以水过去.建树复杂度$O(n\log^2n)$.

那么K-D Tree怎么查询平面最近点对呢?实际上这是一个很暴力的方法,对于每个节点我们存下它的子树的最小/大的坐标.查询时递归到每个点都更新答案,然后计算出它的左/右子树到这个点的最小距离的可能值,然后若可能值大于目前的$ans$,就不走这棵子树,否则先走可能值较小的子树,再走可能值较大的子树,均摊复杂度$O(\sqrt n)$.

所以总的复杂度为$O(n\log^2n+\sqrt n)$.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
const long long inf=1000000007ll*1000000007ll*2ll;
int t;
int n;
int rt=0;
struct node{
    long long x,y;
}a[MAXN];
int tot=0;
struct node2{
    int l,r;
    long long minx,miny,maxx,maxy;
    node val;
}f[MAXN];
inline void pushup(int p)//计算坐标极值
{
    f[p].minx=f[p].maxx=f[p].val.x,f[p].miny=f[p].maxy=f[p].val.y;
    f[p].minx=min(f[p].minx,min(f[f[p].l].minx,f[f[p].r].minx));
    f[p].maxx=max(f[p].maxx,max(f[f[p].l].maxx,f[f[p].r].maxx));
    f[p].miny=min(f[p].miny,min(f[f[p].l].miny,f[f[p].r].miny));
    f[p].maxy=max(f[p].maxy,max(f[f[p].l].maxy,f[f[p].r].maxy));
}
bool cmp1(node x,node y)//排序函数
{
    return x.x<y.x;
}
bool cmp2(node x,node y)
{
    return x.y<y.y;
}
int build(int dep,int l,int r)//在区间[l,r)建树,注意下标从0开始可以省去很多麻烦
{
    if(l>=r) return 0;
    int mid=(l+r)>>1;
    if(dep&1) sort(a+l,a+r,cmp1);
    else sort(a+l,a+r,cmp2);
    int p=++tot;
    f[p].val=a[mid];
    f[p].l=build(dep+1,l,mid);
    f[p].r=build(dep+1,mid+1,r);
    pushup(p);
    return p;
}
long long ans=inf;
long long dis(long long x1,long long y1,long long x2,long long y2)//两点间的距离
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
long long mindis(int p,long long x,long long y)//子树内的最小可能距离
{
    long long a=max(0ll,f[p].minx-x)+max(0ll,x-f[p].maxx);
    long long b=max(0ll,f[p].miny-y)+max(0ll,y-f[p].maxy);
    return a*a+b*b;
}
void query(int p,long long x,long long y)//查询
{
    if(!p) return;
    ans=min(ans,dis(x,y,f[p].val.x,f[p].val.y));
    long long ld=mindis(f[p].l,x,y),rd=mindis(f[p].r,x,y);//计算每个子树的最小可能距离
    if(ld<rd)//先走距离小的
    {
        if(ld<ans) query(f[p].l,x,y);
        if(rd<ans) query(f[p].r,x,y);
    }
    else
    {
        if(rd<ans) query(f[p].r,x,y);
        if(ld<ans) query(f[p].l,x,y);
    }
}
int main()
{
    f[0].minx=f[0].miny=inf,f[0].maxx=f[0].maxy=0;
    read(t);
    while(t--)
    {
        ans=inf,tot=rt=0;
        read(n);
        for(int i=0;i<n;i++) read(a[i].x),read(a[i].y);
        random_shuffle(a,a+n);
        rt=build(1,0,n);
        for(int i=1;i<=n;i++)
        {
            long long x,y;
            read(x),read(y);
            query(rt,x,y);
        }
        printf("%.3Lf\n",sqrt((long double)ans));
    }
	return 0;
}

扩展

K-D Tree的更多操作概述:

插入节点:按照划分的标准一直往下走,然后插到叶子即可.

删除节点:目前没有很好的做法,但是利用替罪羊树的思想$Rebuild$整棵子树.复杂度均摊下来应该不会太大.

维护平衡:同样采用替罪羊树的$Rebuild$思想即可.