問題一覧 > 通常問題

No.1125 Without Parallelogram

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 16
作問者 : e869120e869120 / テスター : ThistleThistle
0 ProblemId : 4638 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-07-17 23:25:16

問題文

以下の条件を満たす $N$ 個の点の座標を 1 つ出力しなさい。ただし、$i$ 個目 $(1 \leq i \leq N)$ の点の座標を $(x_i, y_i)$ と表すこととする。

  • $x_i, y_i$ は整数である。
  • $0 \leq x_i, y_i \leq N + 40$。
  • すべての点の座標は相異なる。つまり $(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$。
  • どの $4$ つの点を選んでも、平行四辺形を成さない。
条件を満たす出力が複数ある場合は、そのうちのどれを出力しても正解となる。
また、本問題の制約では必ず 1 通り以上の答えが存在することが証明できる。

重要な注意

この問題において、「$4$ 点が平行四辺形を成す」ことは、以下の条件を満たすことである。

  • $4$ 点を適切な順序で並べ、順に頂点 $A, B, C, D$ とするとき、$AB$ と $CD$ が平行であり、$AB$ と $CD$ の長さが等しくなることがある。
つまり、以下の例の通り、面積 $0$ でも平行四辺形を成す場合がある。

例1
　$4$ 点 $(0, 0), (1, 1), (3, 3), (4, 4)$ は平行四辺形を成す。
　なぜなら、$A(0,0), B(1,1), C(4,4), D(3,3)$ とおいたとき、条件を満たすためである。
例2
　$4$ 点 $(0, 0), (1, 1), (3, 3), (5, 5)$ は平行四辺形を成さない。
　なぜなら、条件を満たすような $4$ 点の並べ方は存在しないからである。

入力

$N$

$1$ 行目に、整数 $N$ が与えられる。

出力

以下の形式で $N$ 個の点を出力しなさい。 

$x_1$ $y_1$
$x_2$ $y_2$
$x_3$ $y_3$
: :
$x_N$ $y_N$

つまり、$N$ 行に渡って出力し、$i$ 行目には $i$ 個目の点の座標 $x_i, y_i$ を空白区切りで出力するということである。
ただし、出力は以下の条件を満たさなければならない。

  • $x_i, y_i$ は整数である。
  • $0 \leq x_i, y_i \leq N + 40$。
  • すべての点の座標は相異なる。つまり $(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$
  • どの $4$ つの点を選んでも、平行四辺形にならない。

制約

  • $1 \leq N \leq 3000$
  • 入力はすべて整数

サンプル

サンプル1
入力
4
出力
0 0
3 1
3 2
7 5

出力は以下の図のようになる。

サンプル2
入力
1
出力
0 0

$N = 1$ の場合、$x_1, y_1$ が整数であり、$0 \leq x_1, y_1 \leq 41$ を満たせば、どのような出力でも正解となる。

サンプル3
入力
6
出力
0 0
1 28
9 24
11 46
25 37
42 17

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。