No.869 Two Distances
タグ : / 解いたユーザー数 3
作問者 :
e869120
/ テスター :
tempura_pp
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もしくは右上の雲マークをクリックしてアカウントを作成してください。