P9119 [Spring Test 2023] Christmas Tree

As everyone knows, Christmas in the year 3202 is coming soon, so little $\Omega$ bought a Christmas tree and a wire covered with colorful lights, and plans to wrap this wire around the tree. The Christmas tree can be regarded as a **convex polygon** with $n$ vertices on a 2D plane. These $n$ vertices can be used to fix the wire, and they are numbered $1, \ldots, n$ in **counterclockwise order**. The coordinates of vertex $i$ are $(x_i, y_i)$. Let $k$ be the index of the vertex with the **maximum $y$-coordinate** (if there are multiple such vertices, choose the one with the **smallest index**). It is not guaranteed that the vertex with index $1$ has the smallest $x$-coordinate. The left side of the figure below shows the outline of a Christmas tree, where the vertex with the **maximum $y$-coordinate** has index $k = 5$.  Little $\Omega$ wants to decorate this Christmas tree with the light-covered wire. For aesthetic reasons, she wants the wire to **pass through every vertex exactly once**. To connect to the power supply, the wire must **start from $(x_k, y_k)$**. Formally, she needs to decide a **permutation** $p_1, \cdots, p_n$ of $1, \cdots, n$ such that $p_1 = k$. Then the wire starts from $(x_{p_1}, y_{p_1})$ and passes through $(x_{p_2}, y_{p_2}), \cdots, (x_{p_n}, y_{p_n})$ in order. The wire length is $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$. - Here $\operatorname{d}$ is the **Euclidean distance** on the plane, i.e., $\operatorname{d}((x, y), (x', y')) = \sqrt{(x - x')^2 + (y - y')^2}$. The right side of the figure above shows one possible plan, where the corresponding permutation is $5, 4, 8, 6, 3, 9, 1, 7, 2$. To save cost, she wants you to find, among all possible plans, one that makes the wire length **as short as possible**. If the shortest plan is not unique, you only need to output **any** one of them. **Considering floating-point errors, your answer is accepted if the relative error or absolute error between your plan and the optimal plan in terms of segment lengths does not exceed $10^{-10}$.**

The first line contains a positive integer $n$, representing the number of vertices of the Christmas tree. The next $n$ lines each contain two real numbers $x_i, y_i$ accurate to $9$ digits after the decimal point, representing the coordinates of vertex $i$. The data guarantees that these $n$ points are **pairwise distinct**, and connecting $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ in order forms a **convex polygon**.

Output one line containing $n$ positive integers $p_1, p_2, \cdots, p_n$ separated by single spaces, representing a permutation of $1, \cdots, n$ such that $p_1 = k$, and the wire length $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$ is **minimal** among all possible plans. If such a plan is not unique, output any one of them.

**[Sample 1 Explanation]** In this sample, there are only the two plans shown in the figure below, with permutations $3, 1, 2$ and $3, 2, 1$. The wire lengths are $3 + \sqrt{2}$ and $3 + \sqrt{5}$, and $3 + \sqrt{2} < 3 + \sqrt{5}$. Therefore, the answer permutation is $3, 1, 2$.  **[Constraints]** For all data, it is guaranteed that $3 \le n \le 1000$ and $|x_i|, |y_i| \le 10^7$. |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |1, 2|$4$|None| |3, 4, 5, 6|$9$|None| |7, 8, 9, 10, 11, 12|$18$|None| |13, 14|$10^3$|A| |15, 16|$10^3$|B| |17, 18, 19, 20|$10^3$|None| Special property A: It is guaranteed that there exists a positive integer $m \ge n$ such that the input $n$ vertices correspond to a consecutive segment of vertices of a regular $m$-gon. Special property B: It is guaranteed that $x_1 < x_2 < \cdots < x_n$ and $y_1 > y_2 > \cdots > y_n$. Translated by ChatGPT 5