P4361 [SHOI2015] 激光发生器

题目描述

曾经发明了超能粒子炮・改的发明家 SHTSC 又公开了他的新发明:激光发生器——一种可以产生高能激光的神秘装置。 激光发生器从正上方看是一个无穷大的平面,里面由一个定向激光发射装置和若干个激光偏转装置组成。一个激光发生器的示例如图所示,细箭头表示定向激光发射装置,粗线段表示激光偏转装置。 ![](https://cdn.luogu.com.cn/upload/pic/16401.png) 由定向激光发射装置发射出的激光可以看成是一条射线,如果遇到激光偏转装置就会发生偏转。奇特的是,SHTSC 所使用的激光偏转装置并非像传统的镜子那样遵循反射定律,而是对于每个激光偏转装置,有一个固定的偏转系数 $λ$,其出射角 $β$ 与入射角 $α$ 的关系为 $β=λα$,并且能在这一过程中增强激光的能量。 ![](https://cdn.luogu.com.cn/upload/pic/16402.png) 注意: 1. 入射角是入射光线和反射平面法向量的夹角。 2. 偏转装置的两面均可偏转。 3. 如果激光平行射入偏转装置,则认为没有发生偏转。 4. 如果不平行且照射到了端点,则认为发生偏转。 5. 当 $β>\frac{1}{2}π$ 时,可能会偏转到另一面。 现在 SHTSC 希望你模拟他所设计的激光发生器的工作过程,来帮助他计算激光究竟被哪些激光偏转装置所偏转。

输入格式

输出格式

说明/提示

### 样例解释 如图所示,激光依次被 $1$ 号和 $2$ 号偏转装置偏转。 ![](https://cdn.luogu.com.cn/upload/pic/16403.png) ## 数据规模和约定 对于 $10\%$ 的数据,$n=1$; 对于 $40\%$ 的数据,$a=b=1$; 对于 $100\%$ 的数据,$n \le 100$,所有坐标与 $a$ 和 $b$ 的绝对值不超过 $1000$,$a,b$ 均非零,$dx$ 、$dy$ 不同时为零。保证所有的偏转装置没有交点,且激光发射起始点不在任何偏转装置上。