← 返回题目列表

AtCoder · arc172_d

D. 距离排名

中文机器翻译题面 查看原题

分数: 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},并且它们的顺序正确。