「BZOJ1941」[SDOI2010]Hide and Seek

Description

iPig在大肥猪学校刚上完了无聊的猪文课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏——捉迷藏。

但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉大肥猪学校的地形了,所以giPi只会躲在大肥猪学校内N个隐秘地点,显然iPig也只会在那N个地点内找giPi。游戏一开始,他们从这NN个隐秘地点之中选定一个地点,iPig保持不动,然后giPi用3030秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到(除了这个地点以外的)最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。

由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你大肥猪学校的N个隐秘地点的坐标,请你编程求出iPig的问题。

Input

11行:一个整数NN
2(N+1)2 \sim (N + 1)行:每行两个整数XiX_iYiY_i,表示第ii个地点的坐标。

Output

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

Sample Input

1
2
3
4
5
4
0 0
1 0
0 1
1 1

Sample Output

1
1

HINT

30%30\%的数据中,2N10002 \leq N \leq 1000
100%100\%的数据中,2N1000002 \leq N \leq 1000000Xi,Yi1000000000 \leq X_i, Y_i \leq 100000000
数据保证没有重点。

Solution

Kdtree板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120000;
int n;
struct Pt {
int x, y;
}a[N];
struct T {
int x1, x2, y1, y2;
int l, r;
Pt p;
}t[N];
int tot;
bool cmpx(Pt a, Pt b) {
return a.x < b.x;
}
bool cmpy(Pt a, Pt b) {
return a.y < b.y;
}
void up(int o) {
t[o].x1 = min(t[t[o].l].x1, t[t[o].r].x1);
t[o].x2 = max(t[t[o].l].x2, t[t[o].r].x2);
t[o].y1 = min(t[t[o].l].y1, t[t[o].r].y1);
t[o].y2 = max(t[t[o].l].y2, t[t[o].r].y2);
t[o].x1 = min(t[o].x1, t[o].p.x);
t[o].x2 = max(t[o].x2, t[o].p.x);
t[o].y1 = min(t[o].y1, t[o].p.y);
t[o].y2 = max(t[o].y2, t[o].p.y);
}
int build(int l, int r, bool c) {

int o = ++tot;
int mid = (l + r) >> 1;
if(c) nth_element(a + l, a + mid, a + r + 1, cmpx);
else nth_element(a + l, a + mid, a + r +1, cmpy);
t[o].p = a[mid];
if(l == r) {
t[o].x1 = t[o].x2 = a[l].x;
t[o].y1 = t[o].y2 = a[l].y;
return o;
}
if(l < mid) t[o].l = build(l, mid - 1, c ^ 1);
if(r > mid) t[o].r = build(mid + 1, r, c ^ 1);
up(o);
return o;
}
int getmn(Pt a, int o) {
int res = 0;
res += max(0, t[o].x1 - a.x) + max(0, a.x - t[o].x2);
res += max(0, t[o].y1 - a.y) + max(0, a.y - t[o].y2);
return res;
}
int getmx(Pt a, int o) {
int res = 0;
res += max(abs(a.x - t[o].x1), abs(a.x - t[o].x2));
res += max(abs(a.y - t[o].y1), abs(a.y - t[o].y2));
return res;
}
int cal(Pt a, Pt b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
void qmin(int o, Pt p, int &ans) {
if(t[o].p.x != p.x || t[o].p.y != p.y)
ans = min(ans, cal(p, t[o].p));
int lt = 1e9, rt = 1e9;
if(t[o].l) lt = getmn(p, t[o].l);
if(t[o].r) rt = getmn(p, t[o].r);
if(min(lt, rt) >= ans) return;
if(lt < rt) {
if(t[o].l) qmin(t[o].l, p, ans);
if(t[o].r) qmin(t[o].r, p, ans);
} else {
if(t[o].r) qmin(t[o].r, p, ans);
if(t[o].l) qmin(t[o].l, p, ans);
}
}
void qmax(int o, Pt p, int &ans) {
if(t[o].p.x != p.x || t[o].p.y != p.y)
ans = max(ans, cal(p, t[o].p));
int lt = -1e9, rt = -1e9;
if(t[o].l) lt = getmx(p, t[o].l);
if(t[o].r) rt = getmx(p, t[o].r);
if(max(lt, rt) <= ans) return;
if(lt > rt) {
if(t[o].l) qmax(t[o].l, p, ans);
if(t[o].r) qmax(t[o].r, p, ans);
} else {
if(t[o].r) qmax(t[o].r, p, ans);
if(t[o].l) qmax(t[o].l, p, ans);
}
}
int main() {
t[0].x1 = t[0].y1 = 1e9;
t[0].x2 = t[0].y2 = -1e9;
n = read();
for(int i = 1; i <= n; ++i)
a[i].x = read(), a[i].y = read();
build(1, n, 0);
int ans = 1e9;
for(int i = 1; i <= n; ++i) {
int ans1 = 1e9;
int ans2 = -1e9;
qmin(1, a[i], ans1);
qmax(1, a[i], ans2);
ans = min(ans,ans2 - ans1);
}
writeln(ans);
return 0;
}