問題一覧 > 通常問題

No.1125 Without Parallelogram

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

問題文

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

  • xi,yi は整数である。
  • 0≤xi,yi≤N+40。
  • すべての点の座標は相異なる。つまり (xi,yi)≠(xj,yj) (i≠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 個の点を出力しなさい。 

x1 y1
x2 y2
x3 y3
: :
xN yN

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

  • xi,yi は整数である。
  • 0≤xi,yi≤N+40。
  • すべての点の座標は相異なる。つまり (xi,yi)≠(xj,yj) (i≠j)
  • どの 4 つの点を選んでも、平行四辺形にならない。

制約

  • 1≤N≤3000
  • 入力はすべて整数

サンプル

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

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

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

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

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

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