AT_arc024_4.[ARC024D] バス停

高桥国的高桥王为了改善国内交通，决定设置几个公交站。高桥国的道路只有两种走向：东西向和南北向。从某个基准点向东 $i$ 公里修建了第 $i$ 条南北向的公路，而在北 $j$ 公里修建了第 $j$ 条东西向公路。第 $i$ 条南北路和第 $j$ 条东西路的交点表示为 $(i, j)$。因为道路是无限延伸的，所以任何相交的两条路都有交点。公交站只能设置在这些交点上，并且一个交点至多只能有一个公交站。

目前已经设置了 $N$ 个公交站。但此时高桥王发现了个严重的问题：由于道路太窄，公交车无法转弯，每条线路只能沿一个方向行驶，这样一来，某些公交站之间就成了孤立的，无法互相流通。这是非常不便的，因此需要增设一些公交站，使得任意两个公交站之间，即使需要换乘也能到达，而换乘后的总距离应等于它们之间的曼哈顿距离。也就是说，对于每对公交站 $(a, b)$ 和 $(c, d)$，必须存在一条换乘路径，使总移动距离为 $|a - c| + |b - d|$ 公里。

受预算限制，总共只能设立 $10,000$ 个公交站，也就是说，还可以再增设 $10,000 - N$ 个公交站。在满足上述条件情况下，找出应该增设的公交站位置。如果有多种方案，任选其一即可。

输入使用以下格式：

$N$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_N$ $y_N$

• 第 1 行是一个整数 $N\ (2 \leq N \leq 1,000)$，表示已经设置好的公交站数量。
• 接下来的 $N$ 行，每行两个整数 $x_i\ (1 \leq x_i \leq 1,000)$ 和 $y_i\ (1 \leq y_i \leq 1,000)$，这表示第 $i$ 个公交站位于交叉点 $(x_i, y_i)$。
• 对于所有 $i \neq j$，都有 $(x_i, y_i) \neq (x_j, y_j)$。
• 至少存在一个可行解。

输出应该新增的公交站位置，格式如下：

$M$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_M$ $y_M$

• 第 1 行是一个整数 $M\ (0 \leq M \leq 10,000 - N)$，表示新增公交站的数量。
• 接下来的 $M$ 行，每行两个整数 $x_i\ (1 \leq x_i \leq 1,000)$ 和 $y_i\ (1 \leq y_i \leq 1,000)$，表示第 $i$ 个新增站位于交叉点 $(x_i, y_i)$。
• 对于所有 $i \neq j$，都有 $(x_i, y_i) \neq (x_j, y_j)$。
• 新增站不能与已有站重合。
• 在总共的 $N+M$ 个公交站中，任意两站之间的最短距离必须等于它们之间的曼哈顿距离。

部分分数

题目包含部分分数：

• 如果能正确解决所有 $2 \leq N \leq 100$ 的测试用例，得 $10$ 分。
• 如果能正确解决所有 $2 \leq N \leq 1,000$ 的测试用例，额外得 $90$ 分，总计 $100$ 分。

示例解释 1

经过公交站 $(1, 1)$ 的公交车只能驶向 $(i, 1)$ 或 $(1, j)$（其中 $i, j$ 是任意整数）。同理，经过站点 $(2, 2)$ 的公交车只能驶向 $(i, 2)$ 或 $(2, j)$。如果增设站点 $(1, 2)$，可以使任何两个站点可达。同样增设站点 $(2, 1)$ 也可以，甚至同时增设这两处也行。

示例解释 2

请注意，新增加的站点之间也必须满足最短路径等于曼哈顿距离的条件。

本翻译由 AI 自动生成