[SDOI2010]捉迷藏 K-Dtree

[SDOI2010]捉迷藏

链接

luogu

思路

k-dtree模板题

代码

#include <bits/stdc++.h>

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

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

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

#define cmax(a,b) (a>b?a:a=b)

using namespace std;

const int N=5e5+7;

const int INF=0x3f3f3f3f;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,rt,WD;

struct point {

	int x[2];

	bool operator < (const point &b) const {

		return x[WD]<b.x[WD];

	}

}p[N];

struct node{

	int mi[2],ma[2],ch[2];

	point a;

}t[N];

void update(int x,int y) {

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

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

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

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

}

void up(int u) {

	t[u].mi[0]=t[u].ma[0]=t[u].a.x[0];

	t[u].mi[1]=t[u].ma[1]=t[u].a.x[1];

	if(ls) update(u,ls);

	if(rs) update(u,rs);

}

int build(int l,int r,int wd) {

	if(l>r) return 0;

	int mid=(l+r)>>1;

	WD=wd;

	nth_element(p+l,p+mid,p+r+1);

	int u=mid;

	t[u].a=p[mid];

	ls=build(l,mid-1,wd^1);

	rs=build(mid+1,r,wd^1);

	up(u);

	return u;

}

int dis(point a,point b) {

	return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);

}

int get_min(int u,point a) {

	int rec=0;

	for(int i=0;i<2;++i)

		rec+=max(t[u].mi[i]-a.x[i],0)+max(a.x[i]-t[u].ma[i],0);

	return rec;

}

int get_max(int u,point a) {

	int rec=0;

	for(int i=0;i<2;++i)

		rec+=max(abs(a.x[i]-t[u].ma[i]),abs(a.x[i]-t[u].mi[i]));

	return rec;

}

int ans1,ans2;

void query_min(point a,int u) {

	if(dis(a,t[u].a)) ans1=min(ans1,dis(a,t[u].a));

	int dl=INF,dr=INF;

	if(ls) dl=get_min(ls,a);

	if(rs) dr=get_min(rs,a);

	if(dl<dr) {

		if(ans1>dl) query_min(a,ls);

		if(ans1>dr) query_min(a,rs);

	} else {

		if(ans1>dr) query_min(a,rs);

		if(ans1>dl) query_min(a,ls);

	}

}

void query_max(point a,int u) {

	ans2=max(ans2,dis(a,t[u].a));

	int dl=-INF,dr=-INF;

	if(ls) dl=get_max(ls,a);

	if(rs) dr=get_max(rs,a);

	if(dl<dr) {

		if(ans2<dr) query_max(a,rs);

		if(ans2<dl) query_max(a,ls);

	} else {

		if(ans2<dl) query_max(a,ls);

		if(ans2<dr) query_max(a,rs);

	}

}

int main() {

	n=read();

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

	rt=build(1,n,0);

	int ans=INF;

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

		ans1=INF,ans2=0;

		query_min(p[i],rt);

		query_max(p[i],rt);

//		printf("(%d,%d) min=%d max=%d\n",p[i].x[0],p[i].x[1],ans1,ans2);

		ans=min(ans,ans2-ans1);

	}

	printf("%d",ans);

	return 0;

}