算法问题实战策略——15.4　练习题：弹球模拟（题目 ID：PINBALL，难度：高）

东赫在玩一种新出的弹球游戏，这种弹球游戏会在一个很大的游戏台中放置几个障碍物，然后让玩家抛进小球，撞击障碍物最多的人获胜。小球和障碍物都是正圆，小球撞击障碍物后的入射角和反射角相同。障碍物已固定到游戏台上，不可移动。下图表示东赫依序抛进的小球撞击各障碍物后，弹出游戏台的路线。 给出障碍物的大小和位置，以及小球的位置和方向时，编写程序计算小球撞击的障碍物的序号。小球的半径是1，且只做直线运动。 时间及内存使用限制 程序必须在1秒内完成运算，使用内存不得超过64MB。 输入 第一行输入测试用例的个数C（C≤50）。各测试用例的第一行输入5个整数x、y、dx、dy、N。x、y（0≤x、y≤100）表示当前小球的球心位置，dx、dy（10≤dx、dy≤10）表示小球的方向。当前，小球正在从(x, y)直线滚动到(x+dx, y+dy)。N（0≤N≤50）表示障碍物的个数，每个障碍物都标有0到N1的序号。之后的N行中输入0号到N1号障碍物的信息，每行信息由3个整数xi、yi、ri（0≤xi、yi、ri≤100）组成。此时，第i个障碍物是以(xi, yi）为圆心、半径为ri的圆。 两个障碍物之间的距离不小于2。起始位置上，小球不会与障碍物重叠或接触。 输出 每个测试用例在1行内按照小球撞击障碍物的顺序输出障碍物的序号。如果小球撞击障碍物的次数大于10，那么只输出前10个障碍物的序号。 允许给定的小球和障碍物的大小有小于107的误差。 示例输入值 1 5 5 1 1 5 22 40 12 61 26 20 19 78 21 51 86 7 84 57 15 示例输出值 0 1 2 1 2 0 3 4