问题2615--反射

2615: 反射

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

真实描绘现实中的环境或物体的光影是计算机图形学中一个重要课题,最常用的方法是光线追踪显示法,即当光线进入物体中间时,计算光的路线。试写一个程序计算在特定环境中的路线。 为了简单起见,我们将仅仅考虑二维的情景。所有物体是完全的镜球体,当光线击中这样一种球时,它被完全反射并遵守反射定律,即反射角等于入射角。 你的任务是写一个程序,对给定的特定环境下的光线进入的情况,确定哪些球被光线击中。

输入

第一行包含一个整数n(n <= 25),表示有n个球。 接着的n行每行包含三个整数xi,yi,ri,表示一个球的数据,(xi,yi)是球心坐标,ri > 0是球心半径。 最后一行包含四个整数:x y dx dy,用于描述光线,光线起源于点(x,y),并且前进的方向的增量是(dx,dy).dx,dy至少一个是非0. 这些球都是分离的不接触的,开始时光线不会在球内,并且永远不会与球相切。

输出

输出只有一行。按被光线击中的顺序,打印光线前10次改变方向时击中的球(球的编号是按它们输入时的顺序号)。如果光线击中至多10个球(然后射向无穷远),则打印“inf”在最后一个它击中的球后。如果光线击中多于10个球,在第10个球之后打印三个点“...”。

样例输入 Copy

3
3 3 2
7 7 1
8 1 1
3 8 1 -4

样例输出 Copy

1 2 1 3 inf

来源/分类