问题陈述
你有一张台球桌。 桌子的比赛区域是矩形的。 这张台球桌很特别,因为它没有口袋,并且比赛区域完全被垫子包围。
你们成功制作了超精密台球机器人。 当您将一些球放在桌子上时,机器会击中其中一个球。 击球在总共移动 10,000 单位距离后停止。
当球与桌子的垫子碰撞时,球的轨道就像镜面反射一样。 当球撞到角球时,球会弹回原来的路线。
你的任务是预测哪个球首先与机器人击中的球碰撞。
输入
输入是一系列数据集。 数据集数量小于100。 每个数据集的格式如下。
n w h r v_x v_y x_1 y_1 ... x_n y_n
数据集的第一行包含一个正整数 n,代表桌子上的球数 (2 \leq n \leq 11)。 下一行包含五个整数(w, h, r, v_x, v_y) 用一个空格分隔, 哪里 w 和 h 分别是桌子比赛区域的宽度和长度(4 \leq w, h \leq 1,000), r 是球的半径 (1 \leq r \leq 100)。 机器人以向量 (v_x, v_y) 方向 (-10,000 \leq v_x, v_y \leq 10,000 和 (v_x, v_y) \neq (0, 0) ).
以下 n 线给出了球的位置。 每行由两个由一个空格分隔的整数组成, (x_i, y_i) 表示中心位置 i初始状态下桌子上的第一个球(r < x_i < w - r, r < y_i < h - r). (0, 0) 表示比赛区域西北角的位置, 和 (w, h) 表示比赛区域东南角的位置。 您可以假设,在初始状态下,球不会相互接触,也不会接触垫子。
机器人始终击中列表中的第一个球。 您可以假设给定的值没有错误。
输入的结尾由包含单个零的行指示。
输出
对于每个数据集,打印第一个与机器人击中的球碰撞的球的索引。
当击中的球与无球碰撞直至停止时,打印 -1.
您可以假设不会有超过一个球同时首先与击球发生碰撞。
还可以保证,当 r 更改为 eps (eps < 10^{-9}), 首先碰撞的球和碰撞的方式不会改变。
示例输入
3 26 16 1 8 4 10 6 9 2 9 10 3 71 363 4 8 0 52 238 25 33 59 288 0
样本输入的输出
3 -1