AT_agc047_f [AGC047F] Rooks
题目描述
给你一个无限大的棋盘和 $N$ 个敌方车的位置 $(X_i, Y_i)$。每辆车的攻击范围为这辆车所在的一行与这辆车所在的一列，这些车互不攻击（每行每列最多只有一辆车）。
你要把其中一辆车换成国王，然后让国王不断移动，尽可能多地吃掉其他车。
国王可以向前、向后、向左、向右移动，但是不能走进会被车攻击的格子。另外，如果有一辆车在国王的斜对角方向，国王可以斜着移动并吃掉车，但是 **不能斜着走到空格**。
换句话说，这个国王就像个超级兵，能斜着四个方向吃子，横竖四个方向走动。
对每辆车，假设把它换成国王，求吃掉最多车的情况下，最少需要多少步。
输入格式
输入以如下格式从标准输入给出。
> $N$
> $X_1$ $Y_1$
> $X_2$ $Y_2$
> $\vdots$
> $X_N$ $Y_N$
输出格式
输出 $N$ 行。第 $i$ 行对应将 $(X_i,\ Y_i)$ 处的车替换为国王的情况。该行输出一个整数，即吃掉 $M_i$ 个车所需的最小步数。这里 $M_i$ 表示在这种情况下能够吃掉的最大车数（步数不限）。
说明/提示
### 限制条件
- $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$
- 输入中的所有值均为整数。
### 样例说明 1
请参见下图。当将第 $3$ 个车替换为国王时，最多可以吃掉另外两个车。图中的红色路径是一种最优方案——先吃掉第 $1$ 个车，然后不断向右下方移动，吃掉第 $4$ 个车。此时所需步数为 $7$，这就是输出样例第三个数字。
*$x$ 轴正方向为右，$y$ 轴正方向为上*
如果将第 $2,5,6$ 个车替换为国王，则无法吃掉任何其他车，此时最小步数为 $0$。