UOJ Logo Universal Online Judge

UOJ

#610. 【JOISC2021】特技飞行

附件下载 统计

Bitaro 将要参加一场特技飞行比赛。在这场比赛中,他将会驾驶一架飞机。这架飞机将会保持一个确定的海拔高度,并从上空经过检查点。
我们不妨假定这架飞机飞过的区域是一个平面直角坐标系。其中有 $N$ 个检查点,以 $1$ 到 $N$ 编号。第 $i$($1 \le i \le N$)个检查点的坐标为 $(X_i, Y_i)$。

在比赛的过程中,他的飞机必须恰好经过每个检查点一次。具体地,他必须以以下方式飞行:

  1. 首先,Bitaro 选择一个检查点作为起点,并且从这个检查点开始飞行。

  2. 重复以下过程 $N-1$ 次:
    Bitaro 在所有还没有被选择过的检查点中选择一个检查点作为下一个目标,然后从当前检查点直线飞行到这个检查点。

  3. 当飞机到达最后一个检查点时,此次飞行结束。

在第 $2$ 步中,我们认为起点是已经被选择过的。他的飞机必须以直线从一个检查点飞到下一个检查点。虽然这是特技飞行,但是他被禁止在途中画弧线或转弯。

显然,他的飞行路线是一条折线。在飞行的过程中,他的飞机最多会更改 $N-2$ 次他的飞行方向。如果折线中以某个检查点为顶点的角非常小,那么 Bitaro 将会大幅度改换他的飞行方向;并且由于 Bitaro 技艺不精,这很可能会发生事故导致比赛被淘汰。

因此,Bitaro 希望最大化他的折线中最小角(除去起点和终点)的角度。

给定检查点的坐标,请您寻找一个经过检查点的排列顺序使得折线中最小角最大。

输入格式

第一行两个整数 $N, Z_0$。其中 $Z_0$ 是一个供评分器使用的参数。

接下来 $N$ 行,每行两个整数 $X_i,Y_i$。

输出格式

输出包含 $N$ 行。其中第 $k$($1 \le k \le N$)行包含一个整数 $P_k$($1 \le P_k \le N$),即您给出的路线中第 $k$ 个检查点的编号。这里,起点即为 $P_1$。

限制与约定

对于所有的数据,满足

  • $3 \le N \le 1\,000$。

  • $\sqrt{X_i^2+Y_i^2} \le 10\,000\,000\ (1 \le i \le N)$。

  • $(X_i,Y_i) \ne (X_j,Y_j)\ (1 \le i < j \le N)$。

  • $1 \le Z_0 \le 179$。

在这道题中,你可以调用一个库,它包含计算三个点确定的角的角度的函数。这个库在压缩包中的 $\texttt{aerobatics.h}$ 文件中。调用规范如下:

  • $\texttt{double GetAngle(int xa, int ya, int xb, int yb, int xc, int yc)}$
    这个函数计算 $\angle BAC$ 的角度。它返回一个实数,保证误差足够小。
    注意确保参数的顺序正确。
    • 关于点 $A$,参数 $\texttt{xa}$ 是 $A$ 的 $x$ 坐标,参数 $\texttt{ya}$ 是 $A$ 的 $y$ 坐标。
    • 关于点 $B$,参数 $\texttt{xb}$ 是 $B$ 的 $x$ 坐标,参数 $\texttt{yb}$ 是 $B$ 的 $y$ 坐标。
    • 关于点 $C$,参数 $\texttt{xc}$ 是 $C$ 的 $x$ 坐标,参数 $\texttt{yc}$ 是 $C$ 的 $y$ 坐标。
    • 如果 $A,B$ 或 $A,C$ 的坐标相等,那么将会得到不可预料的结果。

在你的程序中,你可以使用该库中的 $\texttt{GetAngle}$。当然,你也可以修改这个函数。
不过评分器同样也使用库中的 $\texttt{GetAngle}$ 函数。

样例一

input

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

output

5
3
1
7
6
4
2

限制与约定

对于每个输出文件,您的分数将以以下方式计算。
如果您的输出是错误的,您的分数为 $0$。例如,如果您给出的序列 $P_1,P_2,\dots,P_N$ 不是 $1,2,\dots,N$ 的排列或您的输出格式有误,您将会悲惨地得到 $0$ 分。
如果您的输出是正确的,则令 $Z$ 为折线中的最小角,您的分数将以以下公式计算:

  • 若 $Z \ge Z_0$,您的分数为 $S$。

  • 若 $Z < Z_0$,您的分数为 $S \times \dfrac{f(Z/180)}{f(Z_0/180)}$。

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

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

您此题的分数为您在 $6$ 个输入文件得到的分数之和,四舍五入到最近的整数。

对于每组输入数据,$N,Z_0$ 的值及分数如下表:

子任务编号 输入文件名 $N$ $Z_0$ 分数
$1$ $\texttt{input_01.txt}$ $15$ $100$ $10$
$2$ $\texttt{input_02.txt}$ $200$ $143$ $15$
$3$ $\texttt{input_03.txt}$ $200$ $134$ $15 $
$4$ $\texttt{input_04.txt}$ $1000$ $156$ $20$
$5$ $\texttt{input_05.txt}$ $1000$ $150$ $20 $
$6$ $\texttt{input_06.txt}$ $1000$ $153$ $20$

下载

样例数据下载

请上传你要提交的文件,并命名为 output_01.txt, output_02.txt, output_03.txt, output_04.txt, output_05.txt, output_06.txt。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: