#NOISC2023C. 圣诞树

圣诞树

题目描述

众所周知,3202 年的圣诞节快要到了,因此小 Ω 买了一棵圣诞树和一根挂满了彩灯的电线,并打算把这根电线缠绕在圣诞树上。

圣诞树可以视作一个二维平面上有 nn 个顶点的凸多边形。这 nn 个顶点可以用于固定电线,且按逆时针顺序依次编号为 1,,n1, \cdots, n。其中第 ii 个顶点的坐标为 (xi,yi)(x_i, y_i),记其中 yy 坐标最大的顶点的编号为 kk(若有多个满足条件的顶点,则取编号最小的)。不保证编号为 11 的顶点的 xx 坐标最小。

下图左侧展示了一棵圣诞树的轮廓,其中 yy 坐标最大的顶点的编号为 k=5k = 5

图 2:一棵圣诞树及一种可能的挂电线的方案

小 Ω 希望用挂满了彩灯的电线装饰这棵圣诞树。出于美观性考虑,她希望这根电线经过所有顶点恰好一次;为了连接电源,这根电线需要(xk,yk)(x_k, y_k) 出发。形式化地,她需要决定一个 1,,n1, \cdots, n排列 p1,,pnp_1, \cdots, p_n,满足 p1=kp_1 = k,随后这根电线从 (xp1,yp1)(x_{p_1}, y_{p_1}) 出发,依次经过 (xp2,yp2),,(xpn,ypn)(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}}))}$。

  • 其中 d\operatorname{d} 为平面上的欧几里得距离,即 $\operatorname{d}((x, y), (x', y')) = \sqrt{(x - x')^2 + (y - y')^2}$。

上图右侧展示了一种可能的方案,此时对应的排列为 5,4,8,6,3,9,1,7,25, 4, 8, 6, 3, 9, 1, 7, 2

为了节省成本,她希望你能在所有可能的方案中,给出一种使电线长度最短的方案。如果使电线长度最短的方案不唯一,你只需要求出其中任意一种。

考虑到浮点数产生的误差,你输出的方案与最优方案的线段长度的相对误差或绝对误差不超过 101010^{-10} 时即认为答案正确

输入格式

第一行包含一个正整数 nn,表示圣诞树的顶点数。

接下来 nn 行,其中第 ii 行包含两个精确到小数点后 99 位的实数 xi,yix_i, y_i 表示编号为 ii 的顶点的坐标。

数据保证这 nn 个点两两不同,并且依次连接 (x1,y1),(x2,y2),,(xn,yn)(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n) 将形成一个凸多边形

输出格式

输出一行包含 nn 个由单个空格隔开的正整数 p1,p2,,pnp_1, p_2, \cdots, p_n,表示一个 1,,n1, \cdots, n 的排列,满足 p1=kp_1 = k,且电线的长度 $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$ 在所有可能的方案中最短。如果这样的方案不唯一,请输出其中任意一种方案。

样例 #1

样例输入 #1

3
0.000000000 0.000000000
3.000000000 0.000000000
1.000000000 1.000000000

样例输出 #1

3 1 2

提示

【样例 1 解释】

这一样例中只有下图所示的两种方案,对应排列分别为 3,1,23, 1, 23,2,13, 2, 1,电线长度分别为 3+23 + \sqrt{2}3+53 + \sqrt{5},而 3+2<3+53 + \sqrt{2} < 3 + \sqrt{5}

因此答案对应的排列为 3,1,23, 1, 2

图 3:样例 1 的全部两种可能的方案

【数据范围】

对于所有数据,保证 3n10003 \le n \le 1000xi,yi107|x_i|, |y_i| \le 10^7

测试点编号 nn \le 特殊性质
1, 2 44
3, 4, 5, 6 99
7, 8, 9, 10, 11, 12 1818
13, 14 10310^3 A
15, 16 B
17, 18, 19, 20

特殊性质 A:保证存在正整数 mnm \ge n,使得输入的 nn 个顶点对应正 mm 边形中连续的一段顶点。

特殊性质 B:保证 x1<x2<<xnx_1 < x_2 < \cdots < x_n,且 y1>y2>>yny_1 > y_2 > \cdots > y_n