当前没有测试数据。

题目描述

比塔罗将参加一场特技飞行比赛。飞机始终保持恒定高度，因此可以把飞行过程看成在平面内进行。

平面上给定 $N$ 个检查点，编号为 $1$ 到 $N$。检查点 $i$ 的坐标为 $(X_i,Y_i)$。

比赛中，飞机必须恰好经过每个检查点一次。比塔罗可以自行选择起点。此后，只要仍有未访问的检查点，他就选择下一个检查点，飞机沿直线从当前检查点飞到该点。飞机到达最后一个检查点后，飞行结束。

因此，飞机的航线是一条折线。在折线的每个内部顶点，也就是除第一个和最后一个检查点之外的每个已访问检查点，飞机都需要改变方向。若该处的夹角很小，转弯就会非常急，飞行也会更加危险。

比塔罗希望让所有内部夹角中的最小值尽可能大。

你会得到用于评分的 6 个固定输入文件。对于每个输入文件，需要给出一个较好的检查点访问顺序。

输入格式

每个输入文件的第一行包含两个整数：

N Z0

其中：

• $N$ 为检查点数量；
• $Z_0$ 为评分时使用的目标角度，单位为度。

接下来 $N$ 行，第 $i$ 行包含两个整数：

Xi Yi

表示检查点 $i$ 的坐标。

输出格式

对于每个输入文件，输出文件必须恰好包含 $N$ 行。

第 $k$ 行输出一个整数 $P_k$，表示航线中第 $k$ 个经过的检查点编号。

$P_1,P_2,\ldots,P_N$ 必须构成 $1,2,\ldots,N$ 的一个排列，其中 $P_1$ 是起点。

输出文件的提交方式

编号为 xx 的测试，对应输出文件名必须为：

aerobatics.xx.out

测试编号 $1$ 到 $6$ 需要补前导零，例如：

• 第 1 个测试：aerobatics.01.out；
• 第 6 个测试：aerobatics.06.out。

提交时上传一个 ZIP 压缩包，其中可以包含一个或多个输出文件。输出文件必须直接位于压缩包根目录，不能放在子目录中。文件名不符合要求的文件会被忽略。

若某次提交缺少某个测试的输出文件，则该次提交不会改变你在该测试上的已有成绩。对于同一个测试，最终取所有提交中的最好成绩。

数据范围

• $3\le N\le 1000$；
• $\sqrt{X_i^2+Y_i^2}\le 10\,000\,000$；
• 不存在两个坐标完全相同的检查点；
• $1\le Z_0\le 179$。

评分方式

若输出不是一个合法排列，或格式错误，则该测试得 $0$ 分。

对于合法输出，对每个 $2\le k\le N-1$，考虑点 $P_k$ 处由线段 $P_kP_{k-1}$ 与 $P_kP_{k+1}$ 形成的夹角。角度取值不超过 $180^\circ$。

设所有 $N-2$ 个内部夹角中的最小值为 $Z$。

• 若 $Z\ge Z_0$，获得该测试的全部分数；
• 若 $Z<Z_0$，获得该测试分数的以下比例：

$$\frac{f(Z/180)}{f(Z_0/180)},$$

其中

$$f(a)=4a^4+a.$$

六个测试的分值如下：

测试	输入文件	$N$	分值
1	aerobatics.01.in	15	10
2	aerobatics.02.in	200	15
3	aerobatics.03.in
4	aerobatics.04.in	1000	20
5	aerobatics.05.in
6	aerobatics.06.in

总分为六个测试最终得分之和。

辅助函数

原题提供了 aerobatics.h，其中包含函数：

double GetAngle(int xa, int ya,
                int xb, int yb,
                int xc, int yc);

该函数计算 $\angle BAC$ 的度数，其中：

$$A=(x_a,y_a),\quad B=(x_b,y_b),\quad C=(x_c,y_c).$$

检查程序使用相同的角度计算公式。你可以在搜索较优输出的程序中直接使用或修改该函数。

样例

输入

7 90
3 1
2 5
0 2
-1 6
-3 1
-1 -4
4 -2

输出

5
3
1
7
6
4
2

该航线的最小内部夹角出现在检查点 $6$，约为 $68.19859^\circ$。由于 $Z_0=90^\circ$，该输出约能获得该测试 $61.5\%$ 的分数。