Задача

1 /8


Космолёт


Задача

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:
  •  звезда Беллатрикс (250 световых лет от Земли)
  •  звезда Бетельгейзе (643 световых года от Земли)
  •  парная звёздная система Ригель (773 световых года от Земли)
Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

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

 
Примеры
Входные данные Выходные данные
1 3
10 10 10
20 20 20
30 30 30
3 51.962
1 2 3
2 5
20 0 0
10 0 0
40 0 0
30 0 0
50 0 0
4 40.000
2 1 4 3

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

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