分数: 2200 点
问题陈述
您已获得职位 (X_i, Y_i) of N 无限棋盘上的敌方车。 没有两只车会互相攻击(每行或每列最多有一只车)。
你要用一张王替换一张车,然后反复移动王以击败尽可能多的车。
你无法进入正在被车攻击的牢房。 另外,你 无法对角移动到空单元格 (但你可以对角击败车)。
(所以这个国王的移动就像一个超级棋子,在 4 个方向上对角地跳动,并在 4 个方向上水平/垂直移动。)
对于每个车,考虑用国王替换它,并找到最小可能的移动数 需要击败尽可能多的车。
约束
- 2 \leq N \leq 200\,000
- 1 \leq X_i, Y_i \leq 10^6
- X_i \neq X_j
- Y_i \neq Y_j
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
打印 N 行。 的 i-第行用于更换车的场景 (X_i, Y_i) 与你的国王。 这一行应包含一个整数:要击败的最小步数 M_i 车 哪里 M_i 表示在这种情况下(无限时间内)被击败的车的最大可能数量。
示例输入 1
6 1 8 6 10 2 7 4 4 9 3 5 1
示例输出 1
5 0 7 5 0 0
参见下图。 如果我们用国王替换车 3,我们最多可以击败另外两个车。 红色路径是最佳的移动序列之一:击败车 1, 然后继续向下和向右,直到你可以击败车 4。 有 7 个步骤,这是输出中的第三个数字。

x 坐标从左到右增加, 而 y 从下到上增加。
从2号、5号或6号车开始,我们无法击败任何其他车。 最佳移动次数为 0。
示例输入 2
5 5 5 100 100 70 20 81 70 800 1
示例输出 2
985 985 1065 1034 0
示例输入 3
10 2 5 4 4 13 12 12 13 14 17 17 19 22 22 16 18 19 27 25 26
示例输出 3
2 2 9 9 3 3 24 5 0 25