問題一覧 > 通常問題

No.869 ふたつの距離

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 5
作問者 : e869120e869120 / テスター : tempura_pptempura_pp
1 ProblemId : 3322 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-01-11 18:30:32

問題文

E869120 君は「距離 $10$」と「距離 $20$」のふたつの距離が好きです。

さて、以下のような条件を満たすように 二次元座標上に $N$ 個の点を置く方法を $1$ つ構成してください。

  • ユークリッド距離が $10$ 以下であるような点の組は $\frac{N(N-1)}{2}$ 通り中ちょうど $A$ 通りである
  • ユークリッド距離が $20$ 以下であるような点の組は $\frac{N(N-1)}{2}$ 通り中ちょうど $B$ 通りである

この課題の制約下では、必ず解が $1$ つ以上存在することが保障されています。

制約

全ての入力データは以下の制約を満たします。

  • $N$ は $1$ 以上 $1 \ 500$ 以下の整数
  • $A$ は $\frac{N(N-1)}{4}$ 以上 $\frac{N(N-1)}{2}$ 以下の整数
  • $B$ は $A+N$ 以上 $\frac{N(N-1)}{2}$ 以下の整数

入力

$N$ $A$ $B$

出力

$i$ 個目の点を $(x_i, y_i)$ とするとき、以下のように $N$ 行に渡って出力してください。
最後の改行を忘れないこと。 

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

ただし、$-100 \ 000 \leq x_i, y_i \leq 100 \ 000$ を満たさなければなりません。
なお、$x_i, y_i$ の値は整数でなくても構いません。

サンプル

サンプル1
入力
8 14 26
出力
-10.101 0.000
10.101 0.000
0.000 -10.101
0.000 10.101
-3.367 -3.367
-3.367 3.367
3.367 -3.367
3.367 3.367

($1, 5$), ($1, 6$), ($2, 7$), ($2, 8$), ($3, 5$), ($3, 7$), ($4, 6$), ($4, 8$), ($5, 6$), ($7, 8$), ($5, 7$), ($6, 8$), ($5, 8$), ($6, 7$) の $14$ 個の $2$ 点の組に関して、距離が $10$ 以下です。
また、全ての $2$ 点の組の選び方 $28$ 通りのうち、($1, 2$), ($3, 4$) の組を除けば距離が $20$ 以下ですので、$26$ つの組が距離 $20$ 以下です。
よって、この出力は条件を満たします。

サンプル2
入力
24 144 269
出力
6.281 9.863
7.942 7.806
11.181 17.072
19.929 11.307
17.747 2.841
8.606 17.429
0.524 15.436
4.356 14.357
0.151 6.009
15.280 6.294
14.826 11.942
1.611 13.914
16.827 9.176
10.113 12.418
14.879 1.673
19.625 1.160
7.888 3.920
8.966 15.421
0.992 8.895
6.729 15.091
11.736 15.335
8.872 8.612
7.123 13.228
2.970 3.626

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