Дистанционный практикум по программированию

Рендеринг реалистичных изображений воображаемой среды или объектов - интересная тема в компьютерной графике. Одним из самых популярных методов для этой цели является трассировка лучей.

Чтобы визуализировать изображения, используя трассировку лучей, вычисляют (отслеживают) путь, по которому пройдут лучи света, попадающие в сцену. Мы просим вас написать программу, которая вычисляет такие пути.

Для простоты мы рассмотрим только двухмерные сцены. Все объекты в сцене являются полностью отражающими (зеркальными) сферами. Когда луч света попадает на такую сферу, он отражается так, что угол приходящего луча и уходящего луча относительно касательной одинаков:

На следующем рисунке показан типичный путь, по которому луч света может пройти в такой сцене:

Ваша задача - написать программу, которая с учетом описания сцены и луча, входящего в сцену, определит, какие сферы посетит луч.

Исходные данные

Входные данные состоят из набора описаний сцен. Каждое описание начинается со строки, содержащей количество n (n <= 25) сфер в сцене. Следующие n строк содержат три целых числа xi, yi, ri каждая, где (xi, yi) - центр, а ri> 0 - радиус i-й сферы. Далее следует строка, содержащая четыре целых числа x, y, dx, dy, которые описывают луч. Луч исходит из точки (x, y) и изначально указывает в направлении (dx, dy). По крайней мере одно из dx и dy будет отличным от нуля.

Сферы будут непересекающимися и не соприкасающимися. Никакой луч не начинается внутри сферы и не проходит возле сфер по касательной.

Ввод завершается значением n = 0.

Результат

Для каждой сцены сначала выведите номер сцены. Затем выведите номера сфер, по которым луч попадёт в первые десять отражений (нумерация сфер соответствует их порядку на входе).

Если луч попадает не более чем в десять сфер (а затем направляется в бесконечность), выведите inf после последней сферы, в которую он попадает. Если луч достигнет более чем 10 сфер, выведите три точки (...) после десятой сферы.

Выведите пустую строку после каждого теста.

Пример

3
3 3 2
7 7 1
8 1 1
3 8 1 -4
2
0 0 1
5 0 2
2 0 1 0
0

Scene 1
1 2 1 3 inf

Scene 2
2 1 2 1 2 1 2 1 2 1 ...