P9895 [ICPC 2018 Qingdao R] Airdrop

PUBG 是一款多人在线大逃杀视频游戏。在游戏中，最多一百名玩家跳伞到一个岛上，搜寻武器和装备以击杀其他玩家，同时避免自己被击杀。空投是游戏中的一个关键元素，因为空投通常携带强大的武器或大量补给，帮助玩家生存。 考虑游戏的战场是一个二维平面。一个空投刚刚降落在点 $(x_0, y_0)$（$x_0$ 和 $y_0$ 都是整数），战场上的所有 $n$ 名玩家，其中 $(x_i, y_i)$（$x_i$ 和 $y_i$ 都是整数）表示第 $i$ 名玩家的初始位置，开始以以下模式向空投移动： - 如果一个活着的玩家在这个时间单位开始时的位置不等于 $(x_0, y_0)$，他将开始他的下一步移动。 - + 假设他当前在点 $(x, y)$。对于他的下一步移动，他将考虑四个点 $(x, y - 1)$、$(x, y + 1)$、$(x - 1, y)$ 和 $(x + 1, y)$。 - + 他将选择其中一个到空投 $(x_0, y_0)$ 的曼哈顿距离最小的点作为他下一步的目的地。回忆一下，两点 $(x_a, y_a)$ 和 $(x_b, y_b)$ 之间的曼哈顿距离定义为 $|x_a - x_b| + |y_a - y_b|$。 - + 如果两个或更多点到空投的曼哈顿距离相同，他将使用以下优先级规则来打破平局：$(x, y - 1)$ 优先级最高，$(x, y + 1)$ 优先级第二，$(x - 1, y)$ 优先级第三，$(x + 1, y)$ 优先级最低。 - + 在这个时间单位结束时，他到达他的目的地。 - 如果一个活着的玩家在这个时间单位开始时的位置等于 $(x_0, y_0)$，他将继续用空投中的补给填满他的背包，并停留在 $(x_0, y_0)$。 但战斗很激烈，几乎不可能所有玩家都安全到达空投。如果两个或更多玩家在点 $(x', y')$ 相遇，且 $(x', y')$ 不是 $(x_0, y_0)$，他们将互相搏斗并全部阵亡，没有人存活。 BaoBao 是该游戏的忠实粉丝，对成功到达空投位置的玩家数量感兴趣，但他不知道 $x_0$ 的值。给定 $y_0$ 的值和每个玩家的初始位置，请帮助 BaoBao 计算对于所有 $x_0 \in \mathbb{Z}$（$\mathbb{Z}$ 是所有整数的集合，注意 $x_0$ 可以是正数、零或负数），成功到达空投位置的玩家数量的最小值和最大值。

无

无

我们现在解释第一个样例测试用例。 为了得到 $p_\text{min} = 1$ 的答案，应该考虑 $x_0 = 3$。下表显示了当 $x_0 = 3$ 时每个玩家在每个时间单位结束时的位置。 为了得到 $p_\text{max} = 3$ 的答案，应该考虑 $x_0 = 2$。下表显示了当 $x_0 = 2$ 时每个玩家在每个时间单位结束时的位置。 题面翻译由 ChatGPT-4o 提供。