BZOJ1941 [SDOI2010]Hide and Seek

2014.12.24 13:27 Wed| 2 visits oi_2015| 2015_刷题日常| Text

Solution

同样是不能再裸的K-D Tree。连插入操作都没有。直接枚举每一个点,分别询问它到达其他点的最大值和最小值并更新答案。(K-D Tree 的查询操作为什么这么麻烦

Code

#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define inf 0x3f3f3f3f
#define lson(x) (x->ch[0])
#define rson(x) (x->ch[1])
#define son(x,d) (x->ch[d])

inline int read()
{
    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;
}

int pos;
struct point
{
    int x,y;
    point(){}
    point(int _x,int _y):x(_x),y(_y) {}
    point(bool flag):x(read()),y(read()) {}
    bool operator <(const point &p) const
    {
        return pos?y<p.y:x<p.x;
    }
    inline friend ostream &operator <<(ostream &out, const point &p)
    {
        out<<'('<<p.x<<','<<p.y<<')';
        return out;
    }
    inline friend int dist(const point &p1,const point &p2)
    {
        return abs(p1.x-p2.x)+abs(p1.y-p2.y);
    }
};

struct kdtree
{
    point p;
    kdtree *ch[2];
    int l,r,u,d;
    kdtree(){}
    kdtree(const point &_p):p(_p) { l=r=_p.x; u=d=_p.y; }
    void *operator new(size_t size);
    inline void update(int c)
    {
        l=min(l,ch[c]->l); r=max(r,ch[c]->r);
        u=max(u,ch[c]->u); d=min(d,ch[c]->d);
    }
    inline int mindist(const point &_p)
    {
        int re=0;
        if(_p.x<l) re+=l-_p.x;
        else if(_p.x>r) re+=_p.x-r;
        if(_p.y>u) re+=_p.y-u;
        else if(_p.y<d) re+=d-_p.y;
        return re;
    }
    inline int maxdist(const point &_p)
    {
        return max(abs(_p.x-l),abs(_p.x-r))+max(abs(_p.y-u),abs(_p.y-d));
    }
}newnode[N],*null=new kdtree();
void *kdtree::operator new(size_t size)
{
    static kdtree *P=newnode;
    return P++;
}

int n;
point p[N];

kdtree *build(int l,int r,int _pos=0)
{
    if(l>r) return null;
    pos=_pos;
    int mid=(l+r)>>1;
    nth_element(p+l,p+mid,p+r+1);
    kdtree *re=new kdtree(p[mid]);
    lson(re)=build(l,mid-1,_pos^1);
    rson(re)=build(mid+1,r,_pos^1);
    if(lson(re)!=null) re->update(0);
    if(rson(re)!=null) re->update(1);
    return re;
}

void insert(kdtree* &root,point p,int _pos=0)
{
    if(root==null)
    {
        root=new kdtree(p);
        lson(root)=rson(root)=null;
        return;
    }
    pos=_pos;
    if(p<root->p) insert(lson(root),p,_pos^1), root->update(0);
    else insert(rson(root),p,_pos^1), root->update(1);
}

int minans;
void querymin(kdtree *root,point p)
{
    int t=dist(root->p,p);
    if(t) minans=min(minans,t);
    int dist[2]={lson(root)==null?inf:lson(root)->mindist(p),
        rson(root)==null?inf:rson(root)->mindist(p)};
    int d=dist[0]>dist[1];
    if(son(root,d)!=null) querymin(son(root,d),p);
    if(son(root,d^1)!=null&&minans>dist[d^1])
        querymin(son(root,d^1),p);
}

int maxans;
void querymax(kdtree *root,point p)
{
    maxans=max(maxans,dist(root->p,p));
    int dist[2]={lson(root)==null?-inf:lson(root)->maxdist(p),
        rson(root)==null?-inf:rson(root)->maxdist(p)};
    int d=dist[0]<dist[1];
    if(son(root,d)!=null) querymax(son(root,d),p);
    if(son(root,d^1)!=null&&maxans<dist[d^1])
        querymax(son(root,d^1),p);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) p[i]=point(true);
    kdtree *root=build(1,n);
    int ans=inf;
    for(int i=1;i<=n;i++)
    {
        minans=inf; maxans=-inf;
        querymax(root,p[i]); querymin(root,p[i]);
        ans=min(ans,maxans-minans);
    }
    cout<<ans<<endl;
}