CF1477C Nezzar and Nice Beatmap

Nezzar 喜欢玩 osu! 这款游戏。 osu! 是在 beatmap 上进行的，beatmap 可以看作是平面上的若干个不同的点组成的数组。如果对于任意连续的三个点 $A,B,C$（按顺序排列），以 $B$ 为顶点的夹角严格小于 $90$ 度，则称这个 beatmap 是“优美的”。  左侧的点 $A,B,C$ 的夹角小于 $90$ 度，因此它们可以作为优美 beatmap 的连续三个点；右侧的点 $A',B',C'$ 的夹角大于等于 $90$ 度，因此它们不能作为优美 beatmap 的连续三个点。现在 Nezzar 有一个包含 $n$ 个不同点 $A_1,A_2,\ldots,A_n$ 的 beatmap。Nezzar 想要重新排列这 $n$ 个点，使得排列后的 beatmap 是优美的。 形式化地，你需要找到一个 $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$ 行，每行包含两个整数 $x_i, y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示点 $A_i$ 的坐标。 保证所有点互不相同。

如果无解，输出 $-1$。 否则，输出 $n$ 个整数，表示一个合法的排列 $p$。 如果有多组解，可以输出任意一组。

以下是第一个测试用例的示意图：  请注意，$A_1$、$A_2$ 和 $A_5$ 以 $A_2$ 为顶点的夹角被视为 $0$ 度，而 $A_1$、$A_5$ 和 $A_2$ 以 $A_5$ 为顶点的夹角被视为 $180$ 度。 由 ChatGPT 4.1 翻译