【bzoj1941】[Sdoi2010]Hide and Seek

2015.06.17 16:49 Wed | 32次阅读 | 旧日oi | 固定链接 | 源码

题目大意
给定n个二维平面上的点,求每个点离其它点的最大距离减最小距离,然后取其中的最小值。距离指曼哈顿距离 n<=500000
题解
kdtree轻松搞,枚举每个数求一下最大一下最小就行了。注意求最小的时候不要算上本身,因为没有重点,所以当距离等于0的时候不统计就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
#define N 500005
#define ls t[x].l
#define rs t[x].r
int n,root,ans=inf,D,tmp;
struct node
{
    int l,r,mx[2],mn[2],pla[2];
    int & operator [](int x){return pla[x];}
}p[N];
bool operator < (node a,node b)
{
    return a[D]<b[D];
}
struct KDT
{
    node t[N];
    void update(int x)
    {
        for(int i=0;i<2;i++)
        {
            if(ls) t[x].mn[i]=min(t[x].mn[i],t[ls].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[ls].mx[i]);
            if(rs) t[x].mn[i]=min(t[x].mn[i],t[rs].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[rs].mx[i]);
        }
    }
    int build(int l,int r,int now)
    {
        D=now;
        int mid=(l+r)>>1;
        nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        for(int i=0;i<2;i++) t[mid].mx[i]=t[mid].mn[i]=t[mid][i];
        if(l<mid) t[mid].l=build(l,mid-1,now^1);
        if(mid<r) t[mid].r=build(mid+1,r,now^1);
        update(mid);
        return mid;
    }
    int get_dis(int x,node &p)
    {
        return abs(t[x][0]-p[0])+abs(t[x][1]-p[1]);
    }
    int pre_mx(int x,node &p)
    {
        int tmp=0;
        for(int i=0;i<2;i++) tmp+=max(0,t[x].mx[i]-p[i]);
        for(int i=0;i<2;i++) tmp+=max(0,p[i]-t[x].mn[i]);
        return tmp;
    }
    int pre_mn(int x,node &p)
    {
        int tmp=0;
        for(int i=0;i<2;i++) tmp+=max(0,t[x].mn[i]-p[i]);
        for(int i=0;i<2;i++) tmp+=max(0,p[i]-t[x].mx[i]);
        return tmp;
    }
    void getmx(int x,node &p)
    {
        tmp=max(tmp,get_dis(x,p));
        int dl=0,dr=0;
        if(ls) dl=pre_mx(ls,p);
        if(rs) dr=pre_mx(rs,p);
        if(dl>dr)
        {
            if(dl>tmp&&ls) getmx(ls,p);
            if(dr>tmp&&rs) getmx(rs,p);
        }
        else
        {
            if(dr>tmp&&rs) getmx(rs,p);
            if(dl>tmp&&ls) getmx(ls,p);
        }
    }
    void getmn(int x,node &p)
    {
        if(get_dis(x,p)) tmp=min(tmp,get_dis(x,p));
        int dl=0,dr=0;
        if(ls) dl=pre_mn(ls,p);
        if(rs) dr=pre_mn(rs,p);
        if(dl<dr)
        {
            if(dl<tmp&&ls) getmn(ls,p);
            if(dr<tmp&&rs) getmn(rs,p);
        }
        else
        {
            if(dr<tmp&&rs) getmn(rs,p);
            if(dl<tmp&&ls) getmn(ls,p);
        }
    }
}kd;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i][0],&p[i][1]);
    root=kd.build(1,n,0);
    for(int t,i=1;i<=n;i++) 
    {
        tmp=0;kd.getmx(root,p[i]);t=tmp;
        tmp=inf;kd.getmn(root,p[i]);
        ans=min(ans,t-tmp);
    }
    printf("%d\n",ans);
}```