题目背景

本题是提交答案题。

SPJ modified by wlzhouzhuan

题目描述

在一个平面直角坐标系上，有 $N$ 个点 $(X_i,Y_i)$，小 B 从一个点出发，任意选择一个点作为终点走直线路径过去，并重复这个过程 $N-1$ 次，不难发现这个过程会形成由 $N$ 条线段组成的折线，除了第一个点和最后一个点之外的每一个点都会形成一个夹角 $\alpha_i\ (2 \le i \le n-1)$（小于等于 $180^\circ$ 的那个角，$i$ 即代表第 $i$ 个经过的点），小 B 要求你通过策划折线路径经过的点的顺序求得下面这个式子的最大值：

$$\min\limits_{i=2}^{n-1}\{\alpha_i\}$$

输入格式

第一行两个整数 $N,Z_0$ 代表点数和评分参数（见下方数据规模与约定和评测说明）。

接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表一个点。

输出格式

$N$ 行每行一个整数 $P_k$ 代表第 $k$ 个经过的点的编号。

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

5
3
1
7
6
4
2

提示

样例 1 解释

如下图所示：

最小的夹角在点 $6$ 处，为 $68.19859\cdots^\circ$，根据 $Z_0=90$ 和下方评测方式中的评分参数说明，这个输出可以得到 $61.5\%$ 的分数。

数据规模与约定

对于 $100\%$ 的数据，$3 \le N \le 1000$，$\sqrt{X_i^2+Y_i^2} \le 10^7$，任意两点不重合，$1 \le Z_0 \le 179$。

具体地，本题为提交答案题，共有 $6$ 个测试点：

• 输入文件为 input_01.txt 到 input_06.txt。
• 输出文件为 output_01.txt 到 output_06.txt。
• 每一个测试点的 $N$，$Z_0$ 和分数分别为：

测试点编号	$N$	$Z_0$	分数
$1$	$15$	$100$	$10$
$2$	$200$	$143$	$15$
$3$		$134$
$4$	$1000$	$156$	$20$
$5$		$150$
$6$		$153$

评测参数

本题采用 Special Judge。

感谢 @035966_L3 提供的 Special Judge。

如果您的输出格式有误或者输出的数不是 $1 \sim N$ 等其他错误，您抱铃。

如果您的输出格式是正确的，假设您得到的最小夹角是 $Z$，则您的分数如下：

• 如果 $Z \ge Z_0$，您将得到满分。
• 如果 $Z < Z_0$，设该测试点分数为 $S$，您将得到 $S \times \frac{f(Z/180)}{f(Z_0/180)}$。

定义函数 $f(\alpha)\ (0 \le \alpha \le 1)$ 为：

$$f(\alpha)=4\alpha^4+\alpha$$

评测库

我们额外提供评测库（在文件 aerobatics.h 中），您可以用他计算三个点形成的夹角度数。

调用格式如下：

• double GetAngle(int xb,int yb,int xa,int ya,int xc,int yc) 或 double GetAngle(int xb,int yb,int xc,int yc,int xa,int ya)
  • 这个函数计算 $\angle ABC$，误差足够小。
  • 请保证顺序正确。
  • $(xa,ya)$ 为点 $A$。
  • $(xb,yb)$ 为点 $B$。
  • $(xc,yc)$ 为点 $C$。
  • 如果 $(xa,ya)=(xb,yb)$ 或 $(xa,ya)=(xc,yc)$，那么，嘿，嘿嘿。

附加文件说明

1. 名称：下方附件中的 aerobatics-dist.zip。
   • in & out：样例输入输出。
   • aerobatics.h：评测库。
2. 名称：下方附件中的 aerobatics-data.zip：
   • in：输入数据。

说明

翻译自 第２０回日本情報オリンピック　春季トレーニング合宿 Day1 A 曲芸飛行 (Aerobatics) 的英文版本。