「POI2009 R1」消防站 题解

问题分析

我们有一个 $n \times m$ 的网格城市，所有建筑都位于网格交叉点上。距离计算使用曼哈顿距离：$d((x_1,y_1), (x_2,y_2)) = |x_1-x_2| + |y_1-y_2|$。

对于每个方案，有两个消防站 $A = (x_1,y_1)$ 和 $B = (x_2,y_2)$，需要将 $z$ 个历史建筑分为三类：

• 仅由 $A$ 保护：$d(P,A) < d(P,B)$
• 仅由 $B$ 保护：$d(P,A) > d(P,B)$
• 共同保护：$d(P,A) = d(P,B)$

关键观察

1. 曼哈顿距离的垂直平分线

在曼哈顿距离下，两个点 $A$ 和 $B$ 的垂直平分线由两条斜率为 $\pm 1$ 的直线组成。

对于点 $P = (x,y)$，比较 $d(P,A)$ 和 $d(P,B)$ 等价于比较：

$$|x-x_1| + |y-y_1| \quad \text{vs} \quad |x-x_2| + |y-y_2| $$

2. 坐标变换简化问题

令：

• $u = x + y$（主对角线方向）
• $v = x - y$（副对角线方向）

在这个变换下，曼哈顿距离的比较变得简单。

3. 分类条件推导

经过数学推导，点 $P$ 到 $A$ 和 $B$ 的距离关系可以转化为：

情况1：当 $x_1 + y_1 \neq x_2 + y_2$ 且 $x_1 - y_1 \neq x_2 - y_2$ 时

• $d(P,A) < d(P,B)$ 当且仅当：$$(x+y > \frac{x_1+y_1+x_2+y_2}{2}) \ \text{xor} \ (x-y > \frac{x_1-y_1+x_2-y_2}{2}) $$
• $d(P,A) = d(P,B)$ 当且仅当：$$(x+y = \frac{x_1+y_1+x_2+y_2}{2}) \ \text{or} \ (x-y = \frac{x_1-y_1+x_2-y_2}{2}) $$

情况2：特殊情况下需要单独处理（如 $x_1+y_1 = x_2+y_2$ 或 $x_1-y_1 = x_2-y_2$）

算法设计

方法一：直接计算（适用于 $z, p$ 较小）

对于每个方案，遍历所有建筑，直接计算距离并分类：

for each query (A, B):
    count_A = 0, count_B = 0, count_both = 0
    for each building P:
        dist_A = |P.x - A.x| + |P.y - A.y|
        dist_B = |P.x - B.x| + |P.y - B.y|
        if dist_A < dist_B:
            count_A++
        else if dist_A > dist_B:
            count_B++
        else:
            count_both++
    output count_A, count_B, count_both

复杂度：$O(p \times z)$，在 $p, z \leq 10^5$ 时可能达到 $10^{10}$ 次操作，需要优化。

方法二：坐标变换 + 排序/二分

1. 预处理：

   • 对所有建筑，计算 $u_i = x_i + y_i$ 和 $v_i = x_i - y_i$
   • 对 $u$ 和 $v$ 分别排序

2. 查询处理：

   • 对于每个消防站对 $(A,B)$，计算关键值：
     • $mid_u = \frac{u_A + u_B}{2}$
     • $mid_v = \frac{v_A + v_B}{2}$
   • 使用二分查找统计各个区域的建筑数量

复杂度：$O(z \log z + p \log z)$

方法三：基于不等式的高效实现

利用推导出的不等式条件，可以 $O(1)$ 判断每个建筑属于哪个区域。

实现细节

1. 处理整数除法和边界

由于坐标都是整数，中点计算可能产生小数。需要仔细处理：

• 当 $u_A + u_B$ 为奇数时，垂直平分线不经过整点
• 当 $u_A + u_B$ 为偶数时，垂直平分线经过整点

2. 特殊情况处理

• 如果 $u_A = u_B$，所有点满足 $d(P,A) = d(P,B)$ 当且仅当 $v_P = \frac{v_A+v_B}{2}$
• 如果 $v_A = v_B$，所有点满足 $d(P,A) = d(P,B)$ 当且仅当 $u_P = \frac{u_A+u_B}{2}$

3. 高效计数

使用坐标变换后的不等式，可以通过排序+二分快速统计满足条件的点数：

// 预处理
sort buildings by u = x+y
sort buildings by v = x-y

// 查询
function count_buildings(A, B):
    u_mid = (A.u + B.u) / 2
    v_mid = (A.v + B.v) / 2
    
    // 统计四个象限的点数
    // 使用二分查找在排序数组上快速计数

复杂度分析

• 方法一：$O(p \times z)$，最坏 $10^{10}$，不可行
• 方法二：$O(z \log z + p \log z)$，约 $2 \times 10^6$ 操作，可行
• 空间复杂度：$O(z)$ 存储建筑坐标和变换后的坐标

样例验证

输入

6 5 6 1
1 2
6 5
5 1
3 3
3 4
4 1
2 3 4 3

消防站：$A = (2,3)$, $B = (4,3)$

计算：

• $u_A = 5$, $u_B = 7$, $mid_u = 6$
• $v_A = -1$, $v_B = 1$, $mid_v = 0$

对每个建筑分类：

1. (1,2): u=3, v=-1 → B保护
2. (6,5): u=11, v=1 → B保护
3. (5,1): u=6, v=4 → 共同保护（u=mid_u）
4. (3,3): u=6, v=0 → 共同保护（u=mid_u且v=mid_v）
5. (3,4): u=7, v=-1 → A保护
6. (4,1): u=5, v=3 → B保护

结果：A保护:1, B保护:3, 共同保护:2

与输出 1 3 2 一致。

总结

本题的关键在于：

1. 理解曼哈顿距离下的几何性质
2. 通过坐标变换将距离比较转化为简单的不等式
3. 使用排序和二分查找高效处理大量查询

对于 $p, z \leq 10^5$ 的规模，$O(z \log z + p \log z)$ 的算法是可行的。实现时需要注意整数除法的边界情况处理。