分数: 700 点
问题陈述
地点 N 点 p_1, p_2, \dots, p_N 在 N维空间满足以下条件:
条件 1 点的坐标由之间的整数组成 0 和 10^8,包括在内。
条件 2 对于 (A_1, B_1), (A_2, B_2), \dots, (A_{N(N-1)/2}, B_{N(N-1)/2}) 指定为输入, d(p_{A_1}, p_{B_1}) < d(p_{A_2}, p_{B_2}) < \dots < d(p_{A_{N(N-1)/2}}, p_{B_{N(N-1)/2}}) 必须保留。在这里, d(x, y) 表示点之间的欧氏距离 x 和 y.
可以证明在问题的约束下存在解。如果存在多个解决方案,则只需打印其中之一。
什么是欧氏距离?
点之间的欧氏距离 x 和 y 在 n- 维空间,带坐标 (x_1, x_2, \dots, x_n) 为 x 和 (y_1, y_2, \dots, y_n) 为 y,计算如下 \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \dots + (x_n-y_n)^2}.约束
- 3 \leq N \leq 20
- 1 \leq A_i < B_i \leq N \ (1 \leq i \leq \frac{N(N-1)}{2})
- 所有对 (A_1, B_1), (A_2, B_2), \dots, (A_{N(N-1)/2}, B_{N(N-1)/2}) 是不同的。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N(N-1)/2} B_{N(N-1)/2}
输出
让 (p_{i, 1}, p_{i, 2}, \dots, p_{i, N}) 是点的坐标 p_i。按以下格式打印您的解决方案:
p_{1, 1} p_{1, 2} \cdots p_{1, N}
p_{2, 1} p_{2, 2} \cdots p_{2, N}
\vdots
p_{N, 1} p_{N, 2} \cdots p_{N, N}
示例输入 1
4 1 2 1 3 2 4 3 4 1 4 2 3
示例输出 1
3 2 0 0 9 1 0 0 1 8 0 0 9 8 0 0
在此示例输出中,坐标的第三个和第四个分量均为零,因此解可以在下面的二维图中显示。
d(p_1, p_2) = \sqrt{37}, d(p_1, p_3) = \sqrt{40}, d(p_2, p_4) = \sqrt{49}, d(p_3, p_4) = \sqrt{64}, d(p_1, p_4) = \sqrt{72}, d(p_2, p_3) = \sqrt{113},并且它们的顺序正确。