K. Выстрелы по стенам @ MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005 @ Timus Online Judge

K. Выстрелы по стенам

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ

Производится испытание нового пистолета, который может производить выстрелы с различными скоростями пуль. В некоторые моменты времени происходят выстрелы из начала координат с определёнными горизонтальными скоростями, и в некоторые другие моменты строят стены на горизонтальной площадке — невырожденные отрезки, лежащие на прямых, не проходящих через начало координат. При этом стены могут пересекаться. Для обработки результатов эксперимента необходимо определить, сколько времени летела каждая пуля. Можно считать, что пуля летит с постоянной скоростью.

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

В начале каждой строки написано одно из трёх слов: «shot», «wall» или «end». Число строк не превышает 50000. После слова «shot» следуют две координаты скорости пули. Скорость пули не может равняться нулю. После слова «wall» следуют четыре числа — координаты начала и конца стены. Слово «end» является признаком окончания набора входных данных. Все координаты являются целыми числами, по модулю не превосходящими 10000. Все события записаны в хронологическом порядке, и интервалы времени между событиями больше, чем время, за которое строится стена, и чем время, за которое пуля пролетает расстояние до ближайшей стены или за границу испытательного полигона.

Результат

Для каждого выстрела вывести на отдельной строке одно число — время, которое пролетит пуля, с точностью до 10⁻⁶. Если пуля не попадет ни в какую стену, то вместо числа вывести слово «Infinite».

Пример

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

результат

shot 1 0
wall 1 0 0 1
shot 1 1
shot -1 3
wall 1 0 -1 2
shot -1 3
wall 1 1 -1 1
shot -1 3
wall 2 3 2 -3
wall 3 -2 -3 -2
shot 1 -1
shot 40 -39
shot 9999 -10000
shot -1 -1
shot -3000 -2000
shot -3001 -2000
shot -3000 -2001
shot 1 0
shot 1 1
wall -1 2 10 -10
shot -1 1
shot 0 1
shot 1 1
shot 1 0
shot 1 -1
wall 0 -10000 -10000 0
shot -2 -1
end

Infinite
0.50000000000000000000
Infinite
0.50000000000000000000
0.33333333333333333333
2.00000000000000000000
0.05000000000000000000
0.00020000000000000000
2.00000000000000000000
0.00100000000000000000
Infinite
0.00099950024987506247
1.00000000000000000000
0.50000000000000000000
1.00000000000000000000
0.90909090909090909091
0.43478260869565217391
0.83333333333333333333
2.00000000000000000000
3333.33333333333333333

Автор задачи: Андрей Румянцев
Источник задачи: Petrozavodsk summer training camp, August 2005.