반사

상상 속 환경이나 물체의 사실적인 이미지를 렌더링하는 것은 컴퓨터 그래픽스에서 흥미로운 주제입니다. 이를 위해 가장 널리 쓰이는 방법 중 하나가 광선 추적(ray tracing)입니다.

광선 추적으로 이미지를 렌더링할 때는 장면에 들어온 빛이 나아가는 경로(광선)를 추적하여 계산합니다. 이 문제에서는 제한된 환경에서 그러한 경로를 계산하는 프로그램을 작성합니다.

간단하게 하기 위해 2차원 장면만 다룹니다. 장면 안의 모든 물체는 완전히 반사하는(거울) 구입니다. 광선이 이러한 구에 부딪히면, 접선을 기준으로 입사 광선이 이루는 각과 반사 광선이 이루는 각이 같도록 반사됩니다.

주어진 장면 설명과 장면으로 들어오는 광선에 대해, 광선이 어떤 구들에 부딪히는지 계산하는 프로그램을 작성하세요.

입력은 여러 개의 장면 설명으로 이루어집니다. 각 장면 설명은 장면에 있는 구의 개수 $n$ ($n \le 25$)이 적힌 줄로 시작합니다. 이어지는 $n$개의 줄에는 각각 세 정수 $x_i$ $y_i$ $r_i$가 주어지며, $(x_i, y_i)$는 $i$번째 구의 중심이고 $r_i > 0$은 반지름입니다. 그 다음 줄에는 네 정수 $x$ $y$ $dx$ $dy$가 주어져 광선을 나타냅니다. 광선은 점 $(x, y)$에서 출발하여 처음에 방향 $(dx, dy)$를 향합니다. $dx$와 $dy$ 중 적어도 하나는 0이 아닙니다.

구들은 서로 떨어져 있으며 맞닿지 않습니다. 광선은 구 내부에서 출발하지 않고, 어떤 구와도 접하도록 스치지 않습니다.

$n = 0$으로 시작하는 장면은 입력의 끝을 의미하며, 이 장면은 처리하지 않습니다.

각 장면에 대해 먼저 장면 번호를 출력합니다. 그 다음, 광선이 처음 열 번의 반사 안에서 부딪히는 구들의 번호를 (입력에 주어진 순서대로 매긴 번호로) 출력합니다.

광선이 구를 최대 열 개까지 부딪힌 뒤 무한히 뻗어 나가면, 마지막으로 부딪힌 구 뒤에 inf를 출력합니다. 광선이 구를 열 개보다 많이 부딪히면, 열 번째 구 뒤에 점 세 개(...)를 출력합니다.

연속한 두 장면 사이에는 빈 줄을 하나 출력합니다.