HYSBZ bzoj 1941 Hide and Seek

Problem

www.lydsy.com/JudgeOnline/problem.php?id=1941
vjudge.net/contest/187908#problem/B

Reference

[BZOJ1941][Sdoi2010]Hide and Seek（kd-tree）

Meaning

给出平面上 n 个点，要选其中一个，使得它到其它点的 曼哈顿最远距离和最近距离的差 最小，求这个最小的差。

Analysis

用 K-D树对每个点都求离它最远的点和最近的点的距离，相减更新答案。

Notes

这题集合了 K-D树求最远点和最近点的套路，主要在于那两个估价减枝。
在建树的时候，处理出每个点划分的那个区域里的横、纵坐标的最大、最小值，相当于找到包住这个区域的那个大矩形。
在最远点估价的时候，相当于用这个矩形的四个顶点之一（离目标点最远那个）来估价；在最近点时，相当于判断目标点在不在这个矩形内，如果在，直接不算距离，（某一维）在矩形外才算上目标点（在该维度）离最近的矩形边界的距离。

Code

#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 500000, D = 2, X = 1e8, Y = X;

int idx;

struct node
{
    int v[D];
    bool operator < (const node &rhs) const
    {
        return v[idx] < rhs.v[idx];
    }
} kdt[N], aim;

int lc[N], rc[N], big[N][D], sml[N][D];

void pushup(int p)
{
    for(int i = 0; i < D; ++i)
    {
        int &b = big[p][i], &s = sml[p][i];
        if(~lc[p])
        {
            b = max(b, big[lc[p]][i]);
            s = min(s, sml[lc[p]][i]);
        }
        if(~rc[p])
        {
            b = max(b, big[rc[p]][i]);
            s = min(s, sml[rc[p]][i]);
        }
    }
}

int build(int l, int r, int d)
{
    idx = d & 1;
    int m = l + r >> 1;
    nth_element(kdt + l, kdt + m, kdt + r + 1);
    lc[m] = rc[m] = -1;
    for(int i = 0; i < D; ++i)
        big[m][i] = sml[m][i] = kdt[m].v[i];
    if(l < m)
        lc[m] = build(l, m - 1, d + 1);
    if(r > m)
        rc[m] = build(m + 1, r, d + 1);
    pushup(m);
    return m;
}

inline int manhattan(int p)
{
    return abs(aim.v[0] - kdt[p].v[0]) +
            abs(aim.v[1] - kdt[p].v[1]);
}

int far, near; // 最远距离、最近距离

/* 最远距离的估价 */
int dis_b(int p)
{
    int res = 0;
    for(int i = 0; i < D; ++i)
        res += max(
            abs(aim.v[i] - big[p][i]),
            abs(aim.v[i] - sml[p][i])
        );
    return res;
}

void query_b(int p)
{
    far = max(far, manhattan(p));
    int dl = 0, dr = 0;
    if(~lc[p])
        dl = dis_b(lc[p]);
    if(~rc[p])
        dr = dis_b(rc[p]);
    if(dl > dr)
    {
        if(dl > far)
            query_b(lc[p]);
        if(dr > far)
            query_b(rc[p]);
    }
    else
    {
        if(dr > far)
            query_b(rc[p]);
        if(dl > far)
            query_b(lc[p]);
    }
}

/* 最近距离的估价 */
int dis_s(int p)
{
    int res = 0;
    for(int i = 0; i < D; ++i)
        if(aim.v[i] > big[p][i]) // 超出上边界
            res += aim.v[i] - big[p][i];
        else if(aim.v[i] < sml[p][i]) // 超出下边界
            res += sml[p][i] - aim.v[i];
    return res;
}

void query_s(int p)
{
    // 最近距离不包括到自己的距离
    if(int d = manhattan(p))
        near = min(near, d);
    int dl = X + Y, dr = X + Y;
    if(~lc[p])
        dl = dis_s(lc[p]);
    if(~rc[p])
        dr = dis_s(rc[p]);
    if(dl < dr)
    {
        if(dl < near)
            query_s(lc[p]);
        if(dr < near)
            query_s(rc[p]);
    }
    else
    {
        if(dr < near)
            query_s(rc[p]);
        if(dl < near)
            query_s(lc[p]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> kdt[i].v[0] >> kdt[i].v[1];
    int rt = build(0, n - 1, 0), ans = X + Y;
    for(int i = 0; i < n; ++i)
    {
        aim = kdt[i];
        far = 0;
        near = X + Y;
        query_b(rt);
        query_s(rt);
        ans = min(ans, far - near);
    }
    cout << ans << '\n';
    return 0;
}