题目描述

一头非洲牛羚（$gnu$）是一种外形类似牛的羚羊。里克（$Rick$）是一头坚韧的牛羚，作为牛群的首领，在旱季期间带领牛群前往一个名为"公平视野"（$Fair Sight$，简称$FS$）的更丰美牧场。在前往$FS$的途中，里克需要在多个小型中间觅食站点停留，以便让牛群恢复体力。

迁移调查团队（$MIT$）的研究人员发现，牛羚在两个站点之间的移动距离不能超过$D$个单位。他们还观察到，里克非常执着且严谨地遵循正确的方向。它始终沿直线行进，只在觅食站点停留并可能改变方向。它绝不会带领牛群朝远离$FS$的方向移动——最极端的情况也只会选择与$FS$方向垂直的路径。实际上，它总是从所有可能的站点中选择方向最接近$FS$的站点。然而，为了减少牛群的困惑，里克会排除那些需要转向角度超过$90$度的站点（即使这些站点的方向比其他可行站点更接近$FS$方向）。
给定可能的觅食站点地图$FS$的方向以及牛羚群的起点，你需要帮助迁移调查团队预测牛群的移动路径（直到地图允许的最远位置）。

考虑以下示例：假设里克从站点$3$出发，$D=170.0$。大箭头指向$FS$的方向。从站点$3$出发，只有站点$2$和$5$在距离$D$范围内。里克选择站点$2$，因为从站点$3$到站点$2$的方向比到站点$5$更接近$FS$方向。从站点$2$出发，它不会前往站点$5$，因为该方向指向远离$FS$的方向。接着它前往站点$4$（唯一可行的下一站）。此时站点$1$进入可达范围且方向与$FS$有一定一致性，但由于需要超过$90$度的急转弯（逆时针方向），因此被排除。前往站点$7$不会导致急转弯，但方向远离$FS$，且站点$7$超出距离限制。因此路径在此终止。

输入格式

每个测试用例的第一行包含$5$个数值：

$FS$的方向向量$(Fx, Fy)$ ，站点总数$N$（$1 \leq N \leq 100$），起始站点编号$S$（$1 \leq S \leq N$），相邻站点间的最大距离$D$（实数），接下来的$N$行每行包含两个实数$(x, y)$，表示站点的坐标。

输入以一行$5$个$0$结束。所有实数（包括$FS$的分量和$D$）保留$1$位小数，且范围在$-999999 \leq x, y \leq 999999$内。输入数据已针对退化情况（如转向角度是否严格小于$90$度）进行校验，确保计算结果的确定性（使用单精度浮点运算即可）。

输出格式

每个测试用例的输出占一行，按顺序列出迁移路径中访问的站点编号（用空格分隔）。输出至少包含起始站点。

输入数据 $1$

-100.0 0.0 7 3 170.0  
140.0 120.0  
360.0 120.0  
480.0 180.0  
240.0 240.0  
420.0 240.0  
80.0 300.0  
260.0 300.0  
0 0 0 0 0  

输出数据 $1$

3 2 4  

来源

台湾 2004