bzoj 1941: [Sdoi2010]Hide and Seek — K-D tree

1941: [Sdoi2010]Hide and Seek

Time Limit: 16 Sec  Memory Limit: 162 MB

Description

小猪iPig在PKU刚上完了无聊的猪性代数课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏—捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了,所以giPi只会躲在PKU内n个隐秘地点,显然iPig也只会在那n个地点内找giPi。游戏一开始,他们选定一个地点,iPig保持不动,然后giPi用30秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标,请你编程求出iPig的问题。

Input

第一行输入一个整数N 第2~N+1行,每行两个整数X,Y,表示第i个地点的坐标

Output

一个整数,为距离差的最小值。

Sample Input

4
0 0
1 0
0 1
1 1

Sample Output

1

HINT

对于30%的数据,N<=1000 对于100%的数据,N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2

Source

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 500010
inline int rd()
{
    int x=0,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-'0';ch=getchar();}
    return x*f;
}
struct kdtr{int d[2],mn[2],mx[2],ls,rs;}T[N];
int D,ans=inf,ansmx,ansmn,Q,rt;
bool cmp(kdtr a,kdtr b){return a.d[D]<b.d[D];}
void ud(int p)
{
    int l=T[p].ls,r=T[p].rs;
    for(int i=0;i<2;++i)
    {
        if(l) T[p].mx[i]=max(T[p].mx[i],T[l].mx[i]),T[p].mn[i]=min(T[p].mn[i],T[l].mn[i]);
        if(r) T[p].mx[i]=max(T[p].mx[i],T[r].mx[i]),T[p].mn[i]=min(T[p].mn[i],T[r].mn[i]);
    }
}
void build(int &p,int l,int r,int now)
{
    int mid=l+r>>1;D=now;
    nth_element(T+l,T+mid,T+r+1,cmp);p=mid;
    for(int i=0;i<2;++i) T[p].mx[i]=T[p].mn[i]=T[p].d[i];
    if(l<mid) build(T[p].ls,l,mid-1,now^1);
    if(r>mid) build(T[p].rs,mid+1,r,now^1);
    ud(p);
}
void asmx(int &x,int k){x=0;for(int i=0;i<2;++i) x+=max(abs(T[k].mx[i]-T[Q].d[i]),abs(T[k].mn[i]-T[Q].d[i]));}
void fdmx(int k,int now)
{
    int dis=abs(T[k].d[0]-T[Q].d[0])+abs(T[k].d[1]-T[Q].d[1]),dl=-1,dr=-1;
    if(Q^k) ansmx=max(ansmx,dis);
    if(T[k].ls) asmx(dl,T[k].ls);
    if(T[k].rs) asmx(dr,T[k].rs);
    if(dl>dr)
    {
        if(dl>ansmx) fdmx(T[k].ls,now^1);
        if(dr>ansmx) fdmx(T[k].rs,now^1);
    }
    else
    {
        if(dr>ansmx) fdmx(T[k].rs,now^1);
        if(dl>ansmx) fdmx(T[k].ls,now^1);
    }
}
void asmn(int &x,int k){x=0;for(int i=0;i<2;++i) x+=max(0,T[k].mn[i]-T[Q].d[i])+max(0,T[Q].d[i]-T[k].mx[i]);}
void fdmn(int k,int now)
{
    int dis=abs(T[k].d[0]-T[Q].d[0])+abs(T[k].d[1]-T[Q].d[1]),dl=inf,dr=inf;
    if(Q^k) ansmn=min(ansmn,dis);
    if(T[k].ls) asmn(dl,T[k].ls);
    if(T[k].rs) asmn(dr,T[k].rs);
    if(dl<dr)
    {
        if(dl<ansmn) fdmn(T[k].ls,now^1);
        if(dr<ansmn) fdmn(T[k].rs,now^1);
    }
    else
    {
        if(dr<ansmn) fdmn(T[k].rs,now^1);
        if(dl<ansmn) fdmn(T[k].ls,now^1);
    }
}
int n;
int main()
{
    n=rd();
    for(int i=1;i<=n;++i)
        T[i].d[0]=rd(),T[i].d[1]=rd();
    build(rt,1,n,0);
    for(int i=1;i<=n;++i)
    {
        ansmx=-1;ansmn=inf;Q=i;
        fdmx(rt,0);fdmn(rt,0);
        ans=min(ans,ansmx-ansmn);
    }
    printf("%d\n",ans);
    return 0;
}

评论

还没有任何评论,你来说两句吧

发表评论

衫小寨 出品