B - Bowling 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

平面上にボウリングのピンが何本か立っており、それを 4 人の人が異なる角度から眺めています。 1 人にだけ他の人より遥かに多くのピンが見えることはあるでしょうか。

ピンを単純に xy 平面上の点集合とみなしましょう。 4 人の位置を以下の図に示します。 厳密には、

  • A さんから見ると、y 座標が等しい 2 本のピンは重なって見えます。
  • B さんから見ると、(x 座標 - y 座標) が等しい 2 本のピンは重なって見えます。
  • C さんから見ると、x 座標が等しい 2 本のピンは重なって見えます。
  • D さんから見ると、(x 座標 + y 座標) が等しい 2 本のピンは重なって見えます。

A, B, C, D さんに見えるピンの数をそれぞれ a, b, c, d とします。

以下の条件を全て満たすような何らかのピンの配置を構成してください。

  • d \geq 10 \cdot \max \{ a, b, c \}
  • ピンの本数は 1 本以上 10^5 本以下である。
  • ピンの座標は全て 0 以上 10^9 以下の整数である。
  • 2 本のピンが同じ位置にあることはない。

入力

入力はない。

出力

答えを以下の形式で出力せよ。ここで、N はピンの本数、(x_i, y_i) は i 本目のピンの座標である。

N
x_1 y_1
:
x_N y_N

出力は、問題文中の条件を満たすものでなければならない。

入力例 1












出力例 1
9
1 1
1 5
2 7
4 4
5 3
6 8
7 5
8 2
8 7



この出力例は出力形式を例示するものであり、正解ではありません。


この出力は問題文中の図に対応し、d = 8, a = b = c = 7 です。頑張りましたが、AC には届きません。






Score : 800 points







Problem Statement


There are some number of bowling pins on a plane.
Four people are observing the pins from different angles.
Is it possible that one of the observers sees much more pins than the others?




Let's model the pins as a set of points on an xy-plane.
The image below shows the positions of the four observers.
Formally,


    

  • For observer A, two pins overlap if their y-coordinates are the same.
    • 

  • For observer B, two pins overlap if their values of (x-coordinate minus y-coordinate) are the same.
    • 

  • For observer C, two pins overlap if their x-coordinates are the same.
    • 

  • For observer D, two pins overlap if their values of (x-coordinate plus y-coordinate) are the same.
    • 





Let a, b, c, d be the number of pins the observers A, B, C, D see, respectively.


Construct any arrangement of bowling pins that satisfies the following constraints:


    

  • d \geq 10 \cdot \max \{ a, b, c \}
    • 

  • The number of pins is between 1 and 10^5, inclusive.
    • 

  • The coordinates are integers between 0 and 10^9, inclusive.
    • 

  • No two pins are placed at exactly the same place.
    • 
















Input
There is no input.











Output
Print the answer in the following format, where N is the number of pins and (x_i, y_i) are the coordinates of the i-th pin:


N
x_1 y_1
:
x_N y_N



It must satisfy the conditions in the statement.















Sample Input 1











Sample Output 1
9
1 1
1 5
2 7
4 4
5 3
6 8
7 5
8 2
8 7



This sample output is provided for the sake of showing the output format and is not correct.


It matches the picture in the statement.


Here, d = 8 and a = b = c = 7. Nice try, but not enough to get AC.