Problem Description

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}$.

Input Format

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 Format

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.

3
0.000000000 0.000000000
3.000000000 0.000000000
1.000000000 1.000000000

3 1 2

Hint

[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$.

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