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

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

Входные данные
Первая строка входного файла содержит целое число 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

   Решение

Темы:    [ Три окружности одного радиуса ] [ Три прямые, пересекающиеся в одной точке ] [ Признаки и свойства параллелограмма ]

Сложность: 3+ Классы: 8,9

Прислать комментарий

Условие

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

Решение

Пусть окружности с центрами O₁ и O₂ пересекаются в точке A, окружности с центрами O₂ и O₃ – в точке B, окружности с центрами O₁ и O₃ – в точке C, а M – общая точка трёх окружностей. O₁MO₂A и O₁MO₃C – ромбы, значит,  AO₂ || CO₃.  Следовательно, четырёхугольник AO₂O₃C – параллелограмм. Диагональ AO₃ этого параллелограмма проходит через середину диагонали CO₂. То же верно для отрезка BO₁. Следовательно, прямые AO₃, BO₁ и CO₂ пересекаются в одной точке.

Источники и прецеденты использования