【BZOJ1941】Hide and Seek（KD-Tree）

时间：2023-03-09 04:24:06
【BZOJ1941】Hide and Seek（KD-Tree）

【BZOJ1941】Hide and Seek（KD-Tree）

题面

BZOJ

洛谷

题解

\(KD-Tree\)对于每个点搜一下最近点和最远点就好了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 555555

#define cmin(a,b) (a=(a>b?b:a));

#define cmax(a,b) (a=(a<b?b:a));

#define ls (t[o].ch[0])

#define rs (t[o].ch[1])

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Node{int d[2];}a[MAX];

int D;

bool operator<(Node a,Node b){return a.d[D]<b.d[D];}

struct KD_Node

{

	int mn[2],mx[2],ch[2];

	Node a;

}t[MAX];

int n,rt;

int mxd[MAX],mnd[MAX];

void pushup(int x,int y)

{

	cmin(t[x].mn[0],t[y].mn[0]);cmin(t[x].mn[1],t[y].mn[1]);

	cmax(t[x].mx[0],t[y].mx[0]);cmax(t[x].mx[1],t[y].mx[1]);

}

int Build(int l,int r,int nd)

{

	D=nd;int o=(l+r)>>1;

	nth_element(&a[l],&a[o],&a[r+1]);

	t[o].mn[0]=t[o].mx[0]=t[o].a.d[0]=a[o].d[0];

	t[o].mn[1]=t[o].mx[1]=t[o].a.d[1]=a[o].d[1];

	if(l<o)ls=Build(l,o-1,nd^1),pushup(o,ls);

	if(r>o)rs=Build(o+1,r,nd^1),pushup(o,rs);

	return o;

}

int Dis(Node a,Node b){return abs(a.d[0]-b.d[0])+abs(a.d[1]-b.d[1]);}

int min_Dis(Node a,KD_Node t)

{

	return max(t.mn[0]-a.d[0],0)+max(a.d[0]-t.mx[0],0)+max(t.mn[1]-a.d[1],0)+max(a.d[1]-t.mx[1],0);

}

int max_Dis(Node a,KD_Node t)

{

	return max(abs(a.d[0]-t.mn[0]),abs(a.d[0]-t.mx[0]))+max(abs(a.d[1]-t.mn[1]),abs(a.d[1]-t.mx[1]));

}

int Ans,Min,Max;

void Query_mn(int o,Node a)

{

	int tmp=Dis(a,t[o].a),d[2];

	if(tmp)cmin(Min,tmp);

	if(ls)d[0]=min_Dis(a,t[ls]);else d[0]=1e9;

	if(rs)d[1]=min_Dis(a,t[rs]);else d[1]=1e9;

	tmp=d[0]>=d[1];

	if(d[tmp]<Min)Query_mn(t[o].ch[tmp],a);tmp^=1;

	if(d[tmp]<Min)Query_mn(t[o].ch[tmp],a);tmp^=1;

}

void Query_mx(int o,Node a)

{

	if(Max-Min>=Ans)return;

	int tmp=Dis(a,t[o].a),d[2];

	if(tmp)cmax(Max,tmp);

	if(ls)d[0]=max_Dis(a,t[ls]);else d[0]=0;

	if(rs)d[1]=max_Dis(a,t[rs]);else d[1]=0;

	tmp=d[0]<=d[1];

	if(d[tmp]>Max)Query_mx(t[o].ch[tmp],a);tmp^=1;

	if(d[tmp]>Max)Query_mx(t[o].ch[tmp],a);tmp^=1;

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i].d[0]=read(),a[i].d[1]=read();

	rt=Build(1,n,0);Ans=1e9;

	for(int i=1;i<=n;++i)

	{

		Min=1e9;Query_mn(rt,a[i]);

		Max=000;Query_mx(rt,a[i]);

		Ans=min(Ans,Max-Min);

	}

	printf("%d\n",Ans);

	return 0;

}

相关文章