#2039. 「SHOI2015」激光发生器

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

曾经发明了超能粒子炮・改的发明家 SHTSC 又公开了他的新发明:激光发生器——一种可以产生高能激光的神秘装置。

激光发生器从正上方看是一个无穷大的平面,里面由一个定向激光发射装置和若干个激光偏转装置组成。一个激光发生器的示例如图所示,细箭头表示定向激光发射装置,粗线段表示激光偏转装置。

laser_desc_1.png

由定向激光发射装置发射出的激光可以看成是一条射线,如果遇到激光偏转装置就会发生偏转。奇特的是,SHTSC 所使用的激光偏转装置并非像传统的镜子那样遵循反射定律,而是对于每个激光偏转装置,有一个固定的偏转系数 λ\lambda,其出射角 β\beta 与入射角 α\alpha 的关系为 β=λα\beta = \lambda \alpha,并且能在这一过程中增强激光的能量。

laser_desc_2.png

注意:

  1. 入射角是入射光线和反射平面法向量的夹角。
  2. 偏转装置的两面均可偏转。
  3. 如果激光平行射入偏转装置,则认为没有发生偏转。
  4. 如果不平行且照射到了端点,则认为发生偏转。
  5. β>12π\beta > \frac 1 2 \pi 时,可能会偏转到另一面。

现在 SHTSC 希望你模拟他所设计的激光发生器的工作过程,来帮助他计算激光究竟被哪些激光偏转装置所偏转。

输入格式

第一行四个整数 xxyydxd_xdyd_y,表示定向激光发射装置的位置是 (x,y)(x, y),方向是 (dx,dy)(d_x, d_y)
第二行一个整数 nn,表示一共有 nn 个激光偏转装置。
以下 nn 行,每行五个整数 x1x_1y1y_1x2x_2y2y_2aabb,表示一个激光偏转装置是 (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2) 的一条线段,其偏转系数 λ=ab\lambda = \frac a b

输出格式

一行由空格隔开的若干个整数,表示激光依次照射到的激光偏转装置的编号(按照输入顺序从 11nn 编号)。如果激光被偏转超过 1010 次,则只需输出前 1010 次所照射到的偏转装置的编号。特别地,如果激光没有被任何一个偏转装置所偏转,输出 NONE

样例

样例输入

0 2 1 0
2
0 4 3 1 1 1
4 0 0 -4 1 1

样例输出

1 2

样例解释

如图所示,激光依次被 11 号和 22 号偏转装置偏转。

laser_sample_1.png

数据范围与提示

对于 10%10\% 的数据,n=1n = 1
对于 40%40\% 的数据,a=b=1a = b = 1
对于 100%100\% 的数据,n100n \leq 100,所有坐标与 aabb 的绝对值不超过 10001000aabb 均非零,dxd_xdyd_y 不同时为零。保证所有的偏转装置没有交点,且激光发射起始点不在任何偏转装置上。