/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 次元空間上に N 個の点 p_1, p_2, \dots, p_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 のユークリッド距離を示す。
なお、本問題の制約下では答えが存在することが証明できます。また、答えが複数通りある場合でも、そのうち 1 つを出力すればよいです。
ユークリッド距離とは
n 次元空間上の点 x, y のユークリッド距離は、x の座標を (x_1, x_2, \dots, x_n)、y の座標を (y_1, y_2, \dots, y_n) として、\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 \leq i \leq N) の座標を (p_{i, 1}, p_{i, 2}, \dots, p_{i, N}) とするとき、以下の形式で出力してください。
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
この出力例では座標の第 3、第 4 の成分がすべて 0 なので、以下の 2 次元の図で表すことができます。
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} であり、正しい順番になっています。
Score: 700 points
Problem Statement
Place N points p_1, p_2, \dots, p_N in an N-dimensional space to satisfy the following conditions:
Condition 1 The coordinates of the points consist of integers between 0 and 10^8, inclusive.
Condition 2 For (A_1, B_1), (A_2, B_2), \dots, (A_{N(N-1)/2}, B_{N(N-1)/2}) specified as input, 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}}) must hold. Here, d(x, y) denotes the Euclidean distance between points x and y.
It can be proved that a solution exists under the constraints of the problem. If multiple solutions exist, just print one of them.
What is Euclidean distance?
The Euclidean distance between points x and y in an n-dimensional space, with coordinates (x_1, x_2, \dots, x_n) for x and (y_1, y_2, \dots, y_n) for y, is calculated as \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \dots + (x_n-y_n)^2}.Constraints
- 3 \leq N \leq 20
- 1 \leq A_i < B_i \leq N \ (1 \leq i \leq \frac{N(N-1)}{2})
- All pairs (A_1, B_1), (A_2, B_2), \dots, (A_{N(N-1)/2}, B_{N(N-1)/2}) are distinct.
Input
The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
\vdots
A_{N(N-1)/2} B_{N(N-1)/2}
Output
Let (p_{i, 1}, p_{i, 2}, \dots, p_{i, N}) be the coordinates of point p_i. Print your solution in the following format:
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}
Sample Input 1
4 1 2 1 3 2 4 3 4 1 4 2 3
Sample Output 1
3 2 0 0 9 1 0 0 1 8 0 0 9 8 0 0
In this sample output, the third and fourth components of the coordinates are all zero, so the solution can be shown in the two-dimensional figure below.
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}, and they are in the correct order.