Олимпиадный тренинг

Задача . D. Космические мины


Задача

Темы: геометрия *2500

Давным-давно в одной далекой-предалекой галактике...

Дарт Вейдер обнаружил месторасположение базы повстанцев. Теперь он собирается уничтожить эту базу (а заодно и всю планету, на которой база находится), при помощи Звезды Смерти.

Узнав о приближении Звезды Смерти, повстанцы решили использовать новое секретное оружие — космические мины. Опишем конструкцию космических мин.

Каждая космическая мина имеет форму шара (его мы будем называть телом мины) некоторого радиуса r с центром в точке O, из которого торчат несколько шипов. Каждый шип можно считать отрезком, соединяющим центр мины с некоторой точкой P, такой, что (большая длина шипа затрудняет транспортировку мин), где |OP| — длина отрезка соединяющего O и P. Точку P удобно задавать вектором p, таким, что P = O + p.

Звезда Смерти имеет форму шара радиуса R (R больше радиуса любой мины). Она движется в постоянной скоростью вдоль вектора v со скоростью |v|. На момент обнаружения повстанцами Звезды Смерти, она располагалась в точке A.

Повстанцы расположили n космических мин на пути Звезды Смерти. Можно считать, что мины неподвижны. Звезда Смерти не знает о существовании мин и не может их обнаружить, поэтому не меняет направление своего движения. Как только Звезда Смерти соприкасается с миной (с ее телом или с одним из ее шипов), мина взрывается и уничтожает Звезду Смерти. Соприкосновением считается ситуация, когда в пространстве существует точка, принадлежащая как мине, так и Звезде Смерти. Считается, что Звезда Смести не уничтожена, если она может лететь бесконечно долго без столкновений с минами.

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

Входные данные

В первой строке входных данных находятся 7 целых чисел Ax, Ay, Az, vx, vy, vz, R — начальное положение Звезды Смерти, направление ее движения, а так же ее радиус ( - 10 ≤ vx, vy, vz ≤ 10, |v| > 0, 0 < R ≤ 100).

Во второй строке находится целое число n — количество мин (1 ≤ n ≤ 100). Далее идут n блоков данных, i-ый из них описывает i-ую мину.

Первая строка каждого блока содержит 5 целых чисел Oix, Oiy, Oiz, ri, mi — координаты центра мины, радиус ее тела и количество шипов (0 < ri < 100, 0 ≤ mi ≤ 10). Далее следуют mi строк, описывающих шипы i-ой мины, где j-ая из них описывает j-ый шип и содержит 3 целых числа pijx, pijy, pijz — координаты вектора, куда данный шип направлен ().

Координаты центров мин и центра Звезды Смерти — целые числа, по абсолютному значению не превосходящие 10000. Гарантируется, что R > ri для любого 1 ≤ i ≤ n. Для любых мин i ≠ j выполняется неравенство . В начальный момент времени Звезда Смерти и мины не имеют общих точек.

Выходные данные

Если повстанцам удастся остановить Звезду Смерти при помощи космических мин — выведите время от начала первого обнаружения Звезды Смерти до взрыва.

Если столкновения Звезды Смерти с минами не произойдет — выведите «-1» (без кавычек).

Для ответа допустима абсолютная или относительная погрешность 10 - 6.


Примеры
№Входные данныеВыходные данные
1 0 0 0 1 0 0 5
2
10 8 0 2 2
0 -3 0
2 2 0
20 0 0 4 3
2 4 0
-4 3 0
1 -5 0 
10.0000000000
2 8 8 4 4 4 2 6
1
-2 -2 -1 3 0 
-1
3 30 30 2 1 2 1 20
3
0 0 40 5 1
1 4 4
-10 -40 -5 7 0
100 200 95 8 1
-10 0 0 
74.6757620881

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет