BZOJ 1941 Hide and Seek（KD-tree求最远点对）

1941: [Sdoi2010]Hide and Seek

Time Limit: 16 Sec Memory Limit: 162 MB
Submit: 1453 Solved: 781
[Submit][Status][Discuss]
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

HINT

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

题目链接：BZOJ 1941
发现之前学的$KD-tree$可用性不高，于是又学了个新的模板，原理和之前学的差不多，也是在搜索时对搜索子树进行估值，然后根据估值进行剪枝，虽说写起来是个$BST$，但是时间复杂度据说还是$O(\sqrt N)$的。
代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 500010;
int idx;
struct KD
{
    int ls, rs;
    int d[2], mn[2], mx[2];
} T[N];
struct info
{
    int d[2];
    bool operator<(const info &rhs)const
    {
        return d[idx] < rhs.d[idx];
    }
} arr[N];
int rt, sz, Min, Max;

void init()
{
    rt = sz = 0;
}
inline void pushup(int k)
{
    int ls = T[k].ls, rs = T[k].rs;
    if (ls)
    {
        for (int i = 0; i < 2; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[ls].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[ls].mx[i]);
        }
    }
    if (rs)
    {
        for (int i = 0; i < 2; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[rs].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[rs].mx[i]);
        }
    }
}
void build(int &k, int l, int r, int dim)
{
    k = ++sz;
    int mid = MID(l, r);
    idx = dim;
    nth_element(arr + l, arr + mid, arr + r + 1);
    T[k].d[0] = T[k].mn[0] = T[k].mx[0] = arr[mid].d[0];
    T[k].d[1] = T[k].mn[1] = T[k].mx[1] = arr[mid].d[1];
    T[k].ls = T[k].rs = 0;
    if (l < mid)
        build(T[k].ls, l, mid - 1, dim ^ 1);
    if (mid < r)
        build(T[k].rs, mid + 1, r, dim ^ 1);
    pushup(k);
}
inline int partionMin(const info &tar, int k)
{
    int ret = 0;
    if (tar.d[0] > T[k].mx[0])
        ret += tar.d[0] - T[k].mx[0];
    if (tar.d[0] < T[k].mn[0])
        ret += T[k].mn[0] - tar.d[0];
    if (tar.d[1] > T[k].mx[1])
        ret += tar.d[1] - T[k].mx[1];
    if (tar.d[1] < T[k].mn[1])
        ret += T[k].mn[1] - tar.d[1];
    return ret;
}
inline int partionMax(const info &tar, int k)
{
    int ret = 0;
    ret += max(abs(tar.d[0] - T[k].mx[0]), abs(tar.d[0] - T[k].mn[0]));
    ret += max(abs(tar.d[1] - T[k].mx[1]), abs(tar.d[1] - T[k].mn[1]));
    return ret;
}
inline int dis(const info &a, const KD &b)
{
    return abs(a.d[0] - b.d[0]) + abs(a.d[1] - b.d[1]);
}
void FindMin(int k, const info &tar)
{
    int dm = dis(tar, T[k]);
    int ls = T[k].ls;
    int rs = T[k].rs;
    int dl = ls ? partionMin(tar, ls) : INF;
    int dr = rs ? partionMin(tar, rs) : INF;
    if (dm)
        Min = min(Min, dm);
    if (dl < dr)
    {
        if (dl < Min)
            FindMin(ls, tar);
        if (dr < Min)
            FindMin(rs, tar);
    }
    else
    {
        if (dr < Min)
            FindMin(rs, tar);
        if (dl < Min)
            FindMin(ls, tar);
    }
}
void FindMax(int k, const info &tar)
{
    int dm = dis(tar, T[k]);
    int ls = T[k].ls;
    int rs = T[k].rs;
    int dl = ls ? partionMax(tar, ls) : 0;
    int dr = rs ? partionMax(tar, rs) : 0;
    if (dm)
        Max = max(Max, dm);
    if (dl > dr)
    {
        if (dl > Max)
            FindMax(ls, tar);
        if (dr > Max)
            FindMax(rs, tar);
    }
    else
    {
        if (dr > Max)
            FindMax(rs, tar);
        if (dl > Max)
            FindMax(ls, tar);
    }
}
int main(void)
{
    int n, i;
    while (~scanf("%d", &n))
    {
        init();
        for (i = 1; i <= n; ++i)
            scanf("%d%d", &arr[i].d[0], &arr[i].d[1]);
        build(rt, 1, n, 0);
        int ans = INT_MAX;
        for (i = 1; i <= n; ++i)
        {
            Min = INF;
            Max = -1;
            FindMin(1, arr[i]);
            FindMax(1, arr[i]);
            ans = min(ans, Max - Min);
        }
        printf("%d\n", ans);
    }
    return 0;
}