問題一覧 > 通常問題

No.869 Two Distances

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 3
作問者 : e869120 / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 3322 / 自分の提出
問題文最終更新日: 2020-01-11 18:30:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 220 (順位表) の他の問題:

Problem Statement

E869120 likes two distances: "distance $10$" and "distance $20$".

Construct $1$ way of placing $N$ points on the two-dimensional coordinate plane so that the following conditions are satisfied.

  • Among the $\frac{N(N-1)}{2}$ pairs of points, exactly $A$ pairs have a Euclidean distance of $10$ or less
  • Among the $\frac{N(N-1)}{2}$ pairs of points, exactly $B$ pairs have a Euclidean distance of $20$ or less

It is guaranteed that at least $1$ solution exists under the constraints of this problem.

Constraints

All input data satisfy the following constraints.

  • $N$ is an integer between $1$ and $1 \ 500$, inclusive
  • $A$ is an integer between $\frac{N(N-1)}{4}$ and $\frac{N(N-1)}{2}$, inclusive
  • $B$ is an integer between $A+N$ and $\frac{N(N-1)}{2}$, inclusive

Input

$N$ $A$ $B$

Output

Letting the $i$-th point be $(x_i, y_i)$, output $N$ lines as follows.
Do not forget the newline at the end.

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

Here, $-100 \ 000 \leq x_i, y_i \leq 100 \ 000$ must be satisfied.
Note that the values of $x_i, y_i$ do not have to be integers.

Sample

Sample 1
Input
8 14 26
Output
-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

The distance is $10$ or less for the following $14$ pairs of $2$ points: ($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$).
Also, among all $28$ ways of choosing a pair of $2$ points, the distance is $20$ or less except for the pairs ($1, 2$), ($3, 4$), so $26$ pairs have a distance of $20$ or less.
Therefore, this output satisfies the conditions.

Sample 2
Input
24 144 269
Output
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もしくは右上の雲マークをクリックしてアカウントを作成してください。