← 返回题目列表

AtCoder · arc024_4

D. 公交车站

中文机器翻译题面 查看原题

問題文

高桥省高桥国王决定设置多个公交车站以改善国内交通。 高桥国有东西走向和南北走向的道路。 只有 2 类型。从某个参考点向东 i 在公里点 i 南北路已铺设,北 j 在公里点 j 东西向道路已铺设。 i 南北大道及 j 东西路交叉口 我们将其表示为 (i, j) 。路是无限长的,所以 2 两条正交路径将在某处相交。 公交车站只设置在十字路口,而且大多数公交车站都位于同一个十字路口。 仅安装 1 公交车站。

现在 N 公交车站已安装。 然而,高桥王意识到自己犯了一个严重的错误。道路太窄,公共汽车无法转弯。 这意味着您只能在任何路线上沿东西向或南北向行驶。 这将创建一个仅可由公共汽车无法到达的公共汽车站。 这很不方便,所以我们将安装几个新的公交车站 2 您可以通过反复换乘公交车在两个公交车站之间移动。请注意,您只能在巴士站换乘巴士。 另外,如果换乘绕路比较远的话也不方便,那么哪一种比较好呢? 2 它将被安装,以便可以在两个公交车站之间换乘公交车,以便总行驶距离等于公交车站之间的曼哈顿距离。 换句话说,哪个 2 1个巴士站 (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 ≦ N ≦ 1,000) 。
  • 2 从线 N 行数过多 i 行是 一个整数,表示第 i 个公交车站的位置 x_i (1 ≦ x_i ≦ 1,000) 和 y_i (1 ≦ y_i ≦ 1,000) 用空格分隔。这是 i 第一个公交车站是十字路口 据说安装在 (x_i, y_i) 。
  • i \neq j 如果 (x_i, y_i) \neq (x_j, y_j) 成立。
  • 解决方案至少是 1 有两个。 如果满足

部分点

针对此问题设置了部分分数。 如果

  • 2 ≦ N ≦ 100 的所有测试用例均得到正确回答 如果所有满足 10 点。
  • 2 ≦ N ≦ 1,000 的测试用例都被正确回答,则进一步 获得 90 点。总共 100 点。

出力

按以下格式输出要添加的公交车站的位置。

M
x_1 y_1
x_2 y_2
:
x_M y_M
  • 1 行包含一个整数,表示要安装的新公交车站的数量。 表示 M (0 ≦ M ≦ 10,000 - N) 。
  • 2 从线 M 行数过多 i 行是 一个整数,表示第 i 公交车站位置的整数 输出 x_i (1 ≦ x_i ≦ 1,000) 和 y_i (1 ≦ y_i ≦ 1,000) 以空格分隔。这是 i 路口公交车站 这意味着它将安装在 (x_i, y_i) 。
  • i \neq j 如果 (x_i, y_i) \neq (x_j, y_j) 必须保留。
  • 新安装的公交车站的位置不得与已安装的公交车站的位置重叠。
  • 已安装的公交车站和新增的公交车站的组合 对于 N+M 巴士站, 2 最短距离也必须等于曼哈顿距离。

入力例1

2
1 1
2 2

出力例1

1
1 2

巴士站 经过 (1, 1) 的巴士 (i, 1) 或 (1, j) 只能访问 ( i, j 是任意整数)。还有公交车站 (2, 2) 的巴士 (i, 2) 或 (2, j) 只能访问 ( i, j 是任意整数)。 如果添加公交车站 (1, 2) , 2 您可以随时来回。 此外, (2, 1) 或者您可以同时添加两者。


入力例2

4
1 1
2 2
3 4
4 3

出力例2

4
1 2
3 2
3 3
4 4

请注意,新添加的公交车站之间的最短路径也必须等于曼哈顿距离。


入力例3

7
2 4
3 2
4 6
5 1
6 5
7 3
8 7

出力例3

15
3 6
8 5
2 2
7 5
2 5
6 6
3 1
5 6
6 2
6 1
7 1
7 2
2 3
6 7
2 6