P4361 [SHOI2015]激光发生器

    • 20通过
    • 62提交
  • 题目提供者 灰狼与蔷薇
  • 评测方式 云端评测
  • 标签 各省省选 2015 上海
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

    注意:

    1.入射角是入射光线和反射平面法向量的夹角。

    2.偏转装置的两面均可偏转。

    3.如果激光平行射入偏转装置,则认为没有发生偏转。

    4.如果不平行且照射到了端点,则认为发生偏转。

    5.当 $β>1/2π$时,可能会偏转到另一面。

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

    输入输出格式

    输入格式:

    第一行四个整数$ x,y,dx,dy $。表示定向激光发射装置的位置是$(x,y)$,方向是$(dx,dy)$。

    第二行一个整数$n$,表示一共有$n$个激光偏转装置。 以下n行,每行六个整数$x1,y1,x2,y2,a,b$,表示一个激光偏转装置是$(x1,y1)$到$(x2,y2)$的一条线段,其偏转系数$\lambda=a/b$。

    $n\leq 100$,所有坐标与$a$和$b$的绝对值不超过$1000$,$a$、$b$均非$0$。保证所有的偏转装置没有交点。激光发射起始点不在任何偏转装置上。方向向量不为零向量。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    0 2 1 0
    2
    0 4 3 1 1 1
    4 0 0 -4 1 1
    输出样例#1: 复制
    1 2

    说明

    样例解释

    如图所示,激光依次被 $1$ 号和 $2$ 号偏转装置偏转。

    数据规模和约定

    对于10%的数据,n=1

    对于40%的数据,a=b=1

    对于100%的数据,n<=100,所有坐标与a和b的绝对值不超过1000,a、b 均非零,$d_x$ 、$d_y$ 不同时为零。保证所有的偏转装置没有交点,且激光发射起始点不在任何偏转装置上。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。