题解 P2479 【[SDOI2010]捉迷藏】
破忆
·
·
题解
【题意】
求 $\min_{i=1}^{n}(\max_{j=1}^{n}dis(p_i,p_j)-\min_{j=1}^{n}dis(p_i,p_j)(i\ne j))$。
## 【分析】
平面上的点可以用 K-D Tree 维护。
求与点 $p_i$ 的距离的最大（小）值，可以在 K-D Tree 上搜索。
### 剪枝1：
对于每个区间，维护覆盖这个点集的矩形的边界。
估价函数设为当前点与该矩形的最近（远）距离，判断当前区间能否产生更优的答案。
### 剪枝2：
遍历到某个节点时，计算两个子节点的估价函数。
先遍历估价函数更优的子节点。
注意搜索最近距离时不能计算重合的点。
## 【算法】
K-D Tree
## 【代码】
```cpp
#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=1e5+5,INF=2147483647;
const DB A=0.75;
int n;
int now1,now2;
int ans=INF;
int D;
struct point{
int x[2];
bool operator !=(point b)const{return x[0]!=b.x[0]||x[1]!=b.x[1];}
}p[maxn],a[maxn];
bool cmp(point x,point y){
return x.x[D]<y.x[D];
}
int max(int x,int y){
return x>y?x:y;
}
int min(int x,int y){
return x<y?x:y;
}
int abs(int x){
return x>0?x:-x;
}
struct KDT{
int tot,rt;
int top,rub[maxn];
struct ele{
point p;
int l,r,s,mi[2],mx[2];
}t[maxn];
#define mid (l+r>>1)
#define ls(k) t[k].l
#define rs(k) t[k].r
#define p(k) t[k].p
#define s(k) t[k].s
int New(){
return top?rub[top--]:++tot;
}
void pushup(int k){
t[k].mi[0]=t[k].mx[0]=p(k).x[0];
t[k].mi[1]=t[k].mx[1]=p(k).x[1];
s(k)=1;
if(ls(k)){
t[k].mi[0]=min(t[k].mi[0],t[ls(k)].mi[0]);
t[k].mi[1]=min(t[k].mi[1],t[ls(k)].mi[1]);
t[k].mx[0]=max(t[k].mx[0],t[ls(k)].mx[0]);
t[k].mx[1]=max(t[k].mx[1],t[ls(k)].mx[1]);
s(k)+=s(ls(k));
}
if(rs(k)){
t[k].mi[0]=min(t[k].mi[0],t[rs(k)].mi[0]);
t[k].mi[1]=min(t[k].mi[1],t[rs(k)].mi[1]);
t[k].mx[0]=max(t[k].mx[0],t[rs(k)].mx[0]);
t[k].mx[1]=max(t[k].mx[1],t[rs(k)].mx[1]);
s(k)+=s(rs(k));
}
}
int build(int l,int r,int d){
if(l>r) return 0;
int x=New();
D=d;
nth_element(p+l,p+mid,p+r+1,cmp);
p(x)=p[mid];
ls(x)=build(l,mid-1,d^1);
rs(x)=build(mid+1,r,d^1);
pushup(x);
return x;
}
void clear(int k,int pos){
if(ls(k)) clear(ls(k),pos);
p[pos+s(ls(k))+1]=p(k);
rub[++top]=k;
if(rs(k)) clear(rs(k),pos+s(ls(k))+1);
}
void check(int &k,int d){
int c=A*s(k);
if(s(ls(k))>c||s(rs(k))>c){
clear(k,0);
k=build(1,s(k),d);
}
}
void insert(int &k,point p,int d){
if(!k){k=New();ls(k)=rs(k)=0,p(k)=p,pushup(k);return;}
if(p.x[d]<=p(k).x[d]) insert(ls(k),p,d^1);
else insert(rs(k),p,d^1);
pushup(k);
check(k,d);
}
int dis1(int x,int y,int x1,int y1,int x2,int y2){
return (x<x1?x1-x:(x>x2?x-x2:0))+(y<y1?y1-y:(y>y2?y-y2:0));
}
void query1(int k,point x){
if(!k) return;
if(dis1(x.x[0],x.x[1],t[k].mi[0],t[k].mi[1],t[k].mx[0],t[k].mx[1])>now1) return;
if(p(k)!=x) now1=min(now1,dis1(x.x[0],x.x[1],p(k).x[0],p(k).x[1],p(k).x[0],p(k).x[1]));
int dl=ls(k)?dis1(x.x[0],x.x[1],t[ls(k)].mi[0],t[ls(k)].mi[1],t[ls(k)].mx[0],t[ls(k)].mx[1]):INF,
dr=rs(k)?dis1(x.x[0],x.x[1],t[rs(k)].mi[0],t[rs(k)].mi[1],t[rs(k)].mx[0],t[rs(k)].mx[1]):INF;
if(dl<=dr){
query1(ls(k),x);
query1(rs(k),x);
}else{
query1(rs(k),x);
query1(ls(k),x);
}
}
int dis2(int x,int y,int x1,int y1,int x2,int y2){
return max(abs(x-x1),abs(x-x2))+max(abs(y-y1),abs(y-y2));
}
void query2(int k,point x){
if(!k) return;
if(dis2(x.x[0],x.x[1],t[k].mi[0],t[k].mi[1],t[k].mx[0],t[k].mx[1])<now2) return;
now2=max(now2,dis2(x.x[0],x.x[1],p(k).x[0],p(k).x[1],p(k).x[0],p(k).x[1]));
int dl=ls(k)?dis2(x.x[0],x.x[1],t[ls(k)].mi[0],t[ls(k)].mi[1],t[ls(k)].mx[0],t[ls(k)].mx[1]):-INF,
dr=rs(k)?dis2(x.x[0],x.x[1],t[rs(k)].mi[0],t[rs(k)].mi[1],t[rs(k)].mx[0],t[rs(k)].mx[1]):-INF;
if(dl>=dr){
query2(ls(k),x);
query2(rs(k),x);
}else{
query2(rs(k),x);
query2(ls(k),x);
}
}
}T;
char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc
int read(){
int ret=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int main(){
freopen("P2479.in","r",stdin);
freopen("P2479.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
a[i].x[0]=read(),a[i].x[1]=read();
T.insert(T.rt,a[i],0);
}
for(int i=1;i<=n;i++){
now1=INF,now2=-INF;
T.query1(T.rt,a[i]),T.query2(T.rt,a[i]);
ans=min(ans,now2-now1);
}
printf("%d\n",ans);
return 0;
}
```