A6747. 「CEOI2013」亚得里亚海
编程题
提高+/省选-
知识点
题目描述
**题目译自 [CEOI2013](https://ceoi2013.hsin.hr/) Day2 T2「[Adriatic](http://ceoi.inf.elte.hu/probarch/13/tasks_day2.pdf)」**
「千岛之国」是克罗地亚旅游业在 1990 年代中期的官方口号。尽管这个口号在事实上不完全准确（克罗地亚的岛屿略多于 1000 个），但岛屿跳跃（从一个岛屿航行到另一个岛屿）确实是夏季非常受欢迎的活动。
在本任务中，亚得里亚海的地图被视为一个由单位正方形组成的网格，共有 $2500$ 行和 $2500$ 列。行号按北到南编号从 $1$ 到 $2500$；列号按西到东编号从 $1$ 到 $2500$。海中有 $N$ 个岛屿，编号为 $1$ 到 $N$，每个岛屿位于网格的某个单位正方形内。岛屿 $K$ 的位置由对应网格正方形的坐标给出行号 $R_{K}$ 和列号 $C_{K}$。没有两个岛屿位于同一位置。
<center>图 1: 下方第一个样例对应的地图</center>
由于风向和海流的影响，只有位于大致西北或东南方向的岛屿之间可以直接航行。更准确地说，如果满足以下两种情况之一，则可以从岛屿 $A$ 直接航行到岛屿 $B$：
- $R_{A} < R_{B}$ 且 $C_{A} < C_{B}$，即岛屿 $B$ 位于岛屿 $A$ 的东南方向。
- $R_{A} > R_{B}$ 且 $C_{A} > C_{B}$，即岛屿 $B$ 位于岛屿 $A$ 的西北方向。
需要注意的是，两岛之间的距离或中间是否有其他岛屿不会影响从一个岛屿跳跃到另一个岛屿的可能性。如果无法直接从 $A$ 跳跃到 $B$，可以通过其他岛屿使用一些跳跃序列从 $A$ 航行到 $B$。从 $A$ 到 $B$ 的航行距离定义为从 $A$ 到 $B$ 所需的最少跳跃次数。
例如，在上图中，从位于第 $2$ 行第 $3$ 列的岛屿出发，可以跳跃到另外四个岛屿，而到剩下两个岛屿的航行距离为两次跳跃。
一个航海大会正在筹备中，组织者正在考虑将大会举办在每个岛屿上。对于每个候选岛屿，他们希望知道：如果其他所有岛屿各派一艘帆船，所有帆船到达该候选岛屿所需的最小跳跃总次数是多少，或者等价地，所有其他岛屿到该候选岛屿的航行距离之和是多少。请编写一个程序，给定 $N$ 个岛屿的位置，对于每个岛屿 $K$，计算所有其他岛屿到岛屿 $K$ 的航行距离之和。
测试数据保证，对于所有岛屿 $A$ 和 $B$，都可以通过某些跳跃序列从 $A$ 航行到 $B$。
「千岛之国」是克罗地亚旅游业在 1990 年代中期的官方口号。尽管这个口号在事实上不完全准确（克罗地亚的岛屿略多于 1000 个），但岛屿跳跃（从一个岛屿航行到另一个岛屿）确实是夏季非常受欢迎的活动。
在本任务中，亚得里亚海的地图被视为一个由单位正方形组成的网格，共有 $2500$ 行和 $2500$ 列。行号按北到南编号从 $1$ 到 $2500$；列号按西到东编号从 $1$ 到 $2500$。海中有 $N$ 个岛屿，编号为 $1$ 到 $N$，每个岛屿位于网格的某个单位正方形内。岛屿 $K$ 的位置由对应网格正方形的坐标给出行号 $R_{K}$ 和列号 $C_{K}$。没有两个岛屿位于同一位置。
<center>图 1: 下方第一个样例对应的地图</center>
由于风向和海流的影响，只有位于大致西北或东南方向的岛屿之间可以直接航行。更准确地说，如果满足以下两种情况之一，则可以从岛屿 $A$ 直接航行到岛屿 $B$：
- $R_{A} < R_{B}$ 且 $C_{A} < C_{B}$，即岛屿 $B$ 位于岛屿 $A$ 的东南方向。
- $R_{A} > R_{B}$ 且 $C_{A} > C_{B}$，即岛屿 $B$ 位于岛屿 $A$ 的西北方向。
需要注意的是，两岛之间的距离或中间是否有其他岛屿不会影响从一个岛屿跳跃到另一个岛屿的可能性。如果无法直接从 $A$ 跳跃到 $B$，可以通过其他岛屿使用一些跳跃序列从 $A$ 航行到 $B$。从 $A$ 到 $B$ 的航行距离定义为从 $A$ 到 $B$ 所需的最少跳跃次数。
例如，在上图中，从位于第 $2$ 行第 $3$ 列的岛屿出发，可以跳跃到另外四个岛屿，而到剩下两个岛屿的航行距离为两次跳跃。
一个航海大会正在筹备中，组织者正在考虑将大会举办在每个岛屿上。对于每个候选岛屿，他们希望知道：如果其他所有岛屿各派一艘帆船，所有帆船到达该候选岛屿所需的最小跳跃总次数是多少，或者等价地，所有其他岛屿到该候选岛屿的航行距离之和是多少。请编写一个程序，给定 $N$ 个岛屿的位置，对于每个岛屿 $K$，计算所有其他岛屿到岛屿 $K$ 的航行距离之和。
测试数据保证，对于所有岛屿 $A$ 和 $B$，都可以通过某些跳跃序列从 $A$ 航行到 $B$。
输入格式
输入的第一行包含一个整数 $N$，表示岛屿的数量。接下来的$N$行每行包含一对整数，分别表示一个岛屿的位置。每个位置由两个范围在 $[1,2500]$ 中的整数构成，分别表示行号和列号。
输出格式
输出应包含 $N$ 行。对于每个岛屿，按照输入顺序，每行输出一个整数，表示所有其他岛屿到该岛屿的航行距离之和。
输入输出样例
输入 #1
7 1 7 7 5 4 5 4 8 6 6 6 1 2 3
输出 #1
16 11 12 11 12 16 8
输入 #2
4 1 1 2 3 3 2 4 4
输出 #2
3 4 4 3
说明/提示
- 对于 $25\%$ 的测试数据，$N\leq 100$。
- 对于 $50\%$ 的测试数据，$N\leq 1500$。
- 对于 $60\%$ 的测试数据，$N\leq 5000$。
- 对于 $80\%$ 的测试数据，$N\leq 25000$。
- 对于 $100\%$ 的测试数据，$3 \leq N \leq 2.5\cdot 10^5$。
- 对于 $50\%$ 的测试数据，$N\leq 1500$。
- 对于 $60\%$ 的测试数据，$N\leq 5000$。
- 对于 $80\%$ 的测试数据，$N\leq 25000$。
- 对于 $100\%$ 的测试数据，$3 \leq N \leq 2.5\cdot 10^5$。