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

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

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

   Решение

Из выпуклого многогранника с 9 вершинами, одна из которых A, параллельными переносами, переводящими A в каждую из остальных вершин, образуется 8 равных ему многогранников. Докажите, что хотя бы два из этих 8 многогранников пересекаются (по внутренним точкам).

   Решение

Страница: 1 2 3 4 5 6 >> [Всего задач: 26]      

Объём треугольной пирамиды 1. Найдите объём пирамиды с вершинами в точках пересечения медиан данной пирамиды.

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

Решение

На левую чашу весов положили две круглых монеты, а на правую — ещё одну, так что весы оказались в равновесии. А какая из чаш перевесит, если каждую из монет заменить шаром того же радиуса? (Все шары и монеты изготовлены целиком из одного и того же материала, все монеты имеют одинаковую толщину.)

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

Решение

Дан трёхгранный угол с вершиной O и точка A на его ребре. По двум другим его рёбрам скользят точки B и C . Найдите геометрическое место точек пересечения медиан треугольников ABC .

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

Решение

В тетраэдр ABCD , длины всех ребер которого не более 100, можно поместить две непересекающиеся сферы диаметра 1. Докажите, что в него можно поместить одну сферу диаметра 1,01.

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

Решение

Из выпуклого многогранника с 9 вершинами, одна из которых A, параллельными переносами, переводящими A в каждую из остальных вершин, образуется 8 равных ему многогранников. Докажите, что хотя бы два из этих 8 многогранников пересекаются (по внутренним точкам).

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

Решение

Страница: 1 2 3 4 5 6 >> [Всего задач: 26]