{"raw_statement":[{"iden":"statement","content":"众所周知，3202 年的圣诞节快要到了，因此小 Ω 买了一棵圣诞树和一根挂满了彩灯的电线，并打算把这根电线缠绕在圣诞树上。\n\n圣诞树可以视作一个二维平面上有 $n$ 个顶点的**凸多边形**。这 $n$ 个顶点可以用于固定电线，且按**逆时针顺序**依次编号为 $1, \\ldots, n$。其中第 $i$ 个顶点的坐标为 $(x_i, y_i)$，记其中 **$y$ 坐标最大**的顶点的编号为 $k$（若有多个满足条件的顶点，则取**编号最小**的）。不保证编号为 $1$ 的顶点的 $x$ 坐标最小。\n\n下图左侧展示了一棵圣诞树的轮廓，其中 **$y$ 坐标最大**的顶点的编号为 $k = 5$。\n\n![图 2：一棵圣诞树及一种可能的挂电线的方案](https://cdn.luogu.com.cn/upload/image_hosting/ayjegrhj.png)\n\n小 Ω 希望用挂满了彩灯的电线装饰这棵圣诞树。出于美观性考虑，她希望这根电线**经过所有顶点恰好一次**；为了连接电源，这根电线需要**从 $(x_k, y_k)$ 出发**。形式化地，她需要决定一个 $1, \\cdots, n$ 的**排列** $p_1, \\cdots, p_n$，满足 $p_1 = k$，随后这根电线从 $(x_{p_1}, y_{p_1})$ 出发，依次经过 $(x_{p_2}, y_{p_2}), \\cdots, (x_{p_n}, y_{p_n})$。此时，电线长度为 $\\sum_{i=1}^{n-1}{\\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$。\n\n- 其中 $\\operatorname{d}$ 为平面上的**欧几里得距离**，即 $\\operatorname{d}((x, y), (x', y')) = \\sqrt{(x - x')^2 + (y - y')^2}$。\n\n上图右侧展示了一种可能的方案，此时对应的排列为 $5, 4, 8, 6, 3, 9, 1, 7, 2$。\n\n为了节省成本，她希望你能在所有可能的方案中，给出一种使电线长度**最短**的方案。如果使电线长度最短的方案不唯一，你只需要求出其中**任意**一种。\n\n**考虑到浮点数产生的误差，你输出的方案与最优方案的线段长度的相对误差或绝对误差不超过 $10^{-10}$ 时即认为答案正确**。\n"},{"iden":"input","content":"第一行包含一个正整数 $n$，表示圣诞树的顶点数。\n\n接下来 $n$ 行，其中第 $i$ 行包含两个精确到小数点后 $9$ 位的实数 $x_i, y_i$ 表示编号为 $i$ 的顶点的坐标。\n\n数据保证这 $n$ 个点**两两不同**，并且依次连接 $(x_1, y_1), (x_2, y_2), \\cdots, (x_n, y_n)$ 将形成一个**凸多边形**。\n"},{"iden":"output","content":"输出一行包含 $n$ 个由单个空格隔开的正整数 $p_1, p_2, \\cdots, p_n$，表示一个 $1, \\cdots, n$ 的排列，满足 $p_1 = k$，且电线的长度 $\\sum_{i=1}^{n-1}{\\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$ 在所有可能的方案中**最短**。如果这样的方案不唯一，请输出其中任意一种方案。\n"},{"iden":"note","content":"**【样例 1 解释】**\n\n这一样例中只有下图所示的两种方案，对应排列分别为 $3, 1, 2$ 或 $3, 2, 1$，电线长度分别为 $3 + \\sqrt{2}$ 和 $3 + \\sqrt{5}$，而 $3 + \\sqrt{2} < 3 + \\sqrt{5}$。\n\n因此答案对应的排列为 $3, 1, 2$。\n\n![图 3：样例 1 的全部两种可能的方案](https://cdn.luogu.com.cn/upload/image_hosting/tcwvp72y.png)\n\n**【数据范围】**\n\n对于所有数据，保证 $3 \\le n \\le 1000$；$|x_i|, |y_i| \\le 10^7$。\n\n|测试点编号|$n \\le$|特殊性质|\n|:-:|:-:|:-:|\n|1, 2|$4$|无|\n|3, 4, 5, 6|$9$|无|\n|7, 8, 9, 10, 11, 12|$18$|无|\n|13, 14|$10^3$|A|\n|15, 16|$10^3$|B|\n|17, 18, 19, 20|$10^3$|无|\n\n特殊性质 A：保证存在正整数 $m \\ge n$，使得输入的 $n$ 个顶点对应正 $m$ 边形中连续的一段顶点。\n\n特殊性质 B：保证 $x_1 < x_2 < \\cdots < x_n$，且 $y_1 > y_2 > \\cdots > y_n$。\n"}],"translated_statement":null,"sample_group":[["3\n0.000000000 0.000000000\n3.000000000 0.000000000\n1.000000000 1.000000000\n","3 1 2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}