|
Название задачи: Кратеры на Луне . |
 |
Условие
Пролетающие время от времени в опасной близости от нашего спутника Луны астероиды захватываются ее гравитационным полем и, будучи ничем не задерживаемы, врезаются с огромной скоростью в лунную поверхность, оставляя в память о себе порядочных размеров кратеры приблизительно круглой формы.
Увлекающийся астрономией профессор З. В. Ездочетов занялся изучением
современной карты участка лунной поверхности. Он решил найти на ней
максимально длинную цепочку вложенных друг в друга кратеров. Зная о Ваших
недюжинных способностях в области построения алгоритмов, за помощью в
решении этой непростой задачи он обратился к Вам.
Входные данные
Первая строка входного файла содержит целое число N – количество кратеров,
отмеченных на карте (1 ≤ N ≤ 500). Следующие N строк содержат описания
кратеров с номерами от 1 до N. Описание каждого кратера занимает отдельную
строку и состоит из трех целых чисел, принадлежащих диапазону [-32768, 32767] и разделенных пробелами. Первые два числа представляют собой
декартовы координаты его центра, а третье – радиус. Все кратеры различны.
Выходные данные
Первая строка выходного файла должна содержать длину искомой цепочки
кратеров, вторая – номера кратеров из этой цепочки, начиная с меньшего
кратера и кончая самым большим. Номера кратеров должны быть разделены
пробелами. Если существует несколько длиннейших цепочек, следует вывести
любую из них.
Пример входного файла
4
0 0 30
-15 15 20
15 10 5
10 10 10
Пример выходного файла
3
3 4 1
Решение
Скачать архив тестов и решений
Построим граф, вершины которого соответствуют кратерам, а дуга из вершины i
в вершину j идет в том и только том случае, когда i-ый кратер целиком лежит
внутри j-го. По условию задачи нам нужно найти длиннейший путь в
полученном ориентированном ациклическом графе. Для этого применяем метод
динамического программирования, используя схему топологической
сортировки [Липский 88, п. 3.4; Кнут 76, п. 2.2.3].
Упражнение
При определении того, лежит ли i-й кратер внутри j-го, не обязательно
применять вычисления с плавающей точкой. Покажите, как организовать эту
проверку, используя лишь целочисленную арифметику диапазона
LongInt, так, чтобы исключить возможность арифметического переполнения.
