P2479 [SDOI2010] 捉迷藏

· · 题解

我们充分发扬人类智慧。

题目要求的式子是 \min\limits_{1\le i\le n}(\max\limits_{1\le j\le n}dis(p_i,p_j)-\min\limits_{1\le j\le n}dis(p_i,p_j))，其中 dis(a,b) 是 a,b 两点间的曼哈顿距离。

我们先将求固定一点的两点间最大曼哈顿的式子 \max\limits_{1\le j\le n}dis(p_i,p_j) 转化一下。

展开 dis(a,b)，得

\max\limits_{1\le j\le n}|p_{i_x}-p_{j_x}|+|p_{i_y}-p_{j_y}|

拆开绝对值，得

\max\limits_{1\le j\le n}(\max\{(p_{i_x}+p_{i_y})−(p_{j_x}+p_{j_y}),(p_{i_x}-p_{i_y})−(p_{j_x}-p_{j_y}),(-p_{i_x}+p_{i_y})−(-p_{j_x}+p_{j_y}),(-p_{i_x}-p_{i_y})−(-p_{j_x}-p_{j_y})\})

根据 \max 的性质，得

\max\{(p_{i_x}+p_{i_y})-\min\limits_{1\le j\le n}(p_{j_x}+p_{j_y}),(p_{i_x}-p_{i_y})-\min\limits_{1\le j\le n}(p_{j_x}-p_{j_y}),(-p_{i_x}+p_{i_y})-\min\limits_{1\le j\le n}(-p_{j_x}+p_{j_y}),(-p_{i_x}-p_{i_y})-\min\limits_{1\le j\le n}(-p_{j_x}-p_{j_y})\}

显然，我们可以 O(n) 预处理求出四个 \min 中的式子，那么查固定一点的两点间最大曼哈顿距离可以 O(1) 实现。

求固定一点的两点间最小曼哈顿距离就可以将点按横坐标升序排序。

根据数学直觉，最小距离中的另一个点在数组中肯定不会离那个固定的点太远，所以我们取固定的点的前 500 个点和后 500 个点枚举即可。

这样速度快得飞起，总时间只花了 670ms 左右，足以通过此题。