← 返回题目列表

Codeforces · 1477/C

C. Nezzar 和 Nice Beatmap

中文机器翻译题面 查看原题

Nezzar 喜欢 osu! 游戏。

奥苏!在节拍图上播放,节拍图可以看作是由平面上不同点组成的数组。如果对于按顺序列出的任意三个连续点 $$$A,B,C$$$,这三个点之间以 $$$B$$$ 为中心的角度严格小于 $$$90$$$ 度,则称该节拍图为“好”。

左侧的点 $$$A,B,C$$$ 的角度小于 $$$90$$$ 度,因此它们可以是漂亮节拍图的三个连续点;右侧点 $$$A',B',C'$$$ 的角度大于或等于 $$$90$$$ 度,因此它们不能是漂亮节拍图的三个连续点。

现在 Nezzar 拥有 $$$n$$$ 不同点 $$$A_1,A_2,\ldots,A_n$$$ 的谱图。 Nezzar 希望重新排序这些 $$$n$$$ 点,以便生成的节拍图很好。

正式来说,您需要找到从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1,p_2,\ldots,p_n$$$,这样beatmap $$$A_{p_1},A_{p_2},\ldots,A_{p_n}$$$ 就不错了。如果不可能,你应该确定它。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5000$$$)。

然后是 $$$n$$$ 行,其中 $$$i$$$- 其中包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — 点 $$$A_i$$$ 的坐标。

保证所有点都是不同的。

输出

如果没有解,则打印$$$-1$$$。

否则,打印 $$$n$$$ 整数,表示有效的排列 $$$p$$$。

如果有多个可能的答案,您可以打印任何一个。

示例

输入 #1

5
0 0
5 0
4 2
2 1
3 0

输出 #1

1 2 5 3 4

注意

这是第一个测试的插图:

请注意,$$$A_1$$$、$$$A_2$$$ 和 $$$A_5$$$ 之间以 $$$A_2$$$ 为中心的角度被视为 $$$0$$$ 度。但是,$$$A_1$$$、$$$A_5$$$ 和 $$$A_2$$$ 之间以 $$$A_5$$$ 为中心的角度被视为 $$$180$$$ 度。