E - すぬけそだて――わっか――
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
あなたは「すぬけそだて」を楽しんでいます。すぬけ君は、驚くほど賢くなりました!
レベルを上げ、めきめきと知力をつけたすぬけ君は、今や様々なビジネスに手を出しています。すぬけ君の一生懸命に働く姿を見たいあなたは、すぬけ君のオフィスを作ってあげることにしました。
ゲーム内通貨を溜めに溜めたあなたは、ついにすぬけ君の居住スペースを設計するためのアイテム「むげんのわっか」を手に入れました。 「むげんのわっか」は任意の長さの平面上の閉曲線として使うことができ、以下の条件を満たすように配置することができます。
- 「むげんのわっか」の点のうち 5000 点以下を選ぶ。選んだ点を柱の点と呼ぶ。柱の点では「むげんのわっか」は直角に曲がらなければならない。また、その他の点で曲がってはならない。
- 2 つの柱の点の間の部分は、x 軸または y 軸に平行でなければならない。
- すべての柱の点は、x 座標と y 座標がともに絶対値が 10^9 以下の整数である平面上の点に配置されなければならない。
- すべての柱の点について、その点の配置される平面上の点を、「むげんのわっか」の他の点が通ってはならない。「むげんのわっか」が、柱の点以外で自己交叉することは許される。
- 「むげんのわっか」によって、平面全体が(外平面も含めて)ちょうど K 個に分割されなければならない。
下図の最初の配置は条件を満たしますが、2 番目や 3 番目の配置は柱の点の配置された点を「むげんのわっか」が二度以上通っているので、条件を満たしません。
K が与えられるので、条件を満たす配置をひとつ求めてください。
制約
- 2 \leq K \leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
K
出力
最初に、柱の点の個数 N を出力せよ。 その後、N 個の柱の点の配置される座標を順に出力せよ。 i 行目には、i 個目の点の配置される x 座標を表す整数と y 座標を表す整数を空白区切りで出力せよ。
入力例 1
3
出力例 1
6 1 5 1 3 5 3 5 1 3 1 3 5
以下の図のように、平面が 3 つの部分に分かれています。
入力例 2
6
出力例 2
12 2 0 0 0 0 2 6 2 6 0 4 0 4 6 6 6 6 4 0 4 0 6 2 6