D - バス停 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋国の高橋王は国内の交通の便を良くするためにいくつかバス停を設置することにしました。 高橋国には東西に走る道路と、南北に走る道路の 2 種類しかありません。ある基準点から東に i キロメートルの地点に i 番目の南北の道路が敷かれており、北に j キロメートルの地点に j 番目の東西の道路が敷かれています。 i 番目の南北の道路と j 番目の東西の道路の交差点を (i, j) と表すことにします。道路は無限に長いのでどの 2 つの直交する道をとってもどこかで交差します。 バス停は交差点にのみ設置し、同じ交差点にはたかだか 1 個までしかバス停を設置しません。

いまちょうど N 個のバス停を設置し終わりました。 しかし、ここで高橋王は重大なミスに気づきます。道路が狭すぎてバスが道を曲がれないのです。 つまり、どの路線も東西もしくは南北のどちらか一方にしか移動できないということになります。 これでは、バスのみで行き来ができないバス停ができてしまいます。 これでは不便なので、新たにいくつかのバス停を設置してどの 2 つのバス停間もバスの乗り換えを繰り返すことで移動できるようにします。なお、バスの乗り換えはバス停でしかできません。 また、その乗り換えが遠回りになっても不便なので、どの 2 つのバス停間も総移動距離がバス停間のマンハッタン距離と等しくなるようなバスの乗り換えが可能になるように設置します。 つまりどの 2 つのバス停 (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