Distance Ranking

AtCoder

IDarc172_d

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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.

![image](https://img.atcoder.jp/arc172/2df65ad4071e638a89d365f0aaecf25f.png)

API Response (JSON)

{
  "problem": {
    "name": "Distance Ranking",
    "description": {
      "content": "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$, i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc172_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Place $N$ points $p_1, p_2, \\dots, p_N$ in an $N$\\-dimensional space to satisfy the following conditions:\n\n> **Condition 1** The coordinates of the points consist of integers between $0$ and $10^8$, i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments