Версия для печати
Убрать все задачи

---

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

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

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

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

Условие

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

Решение

  Пусть BС – меньшее основание,  BA = x  – меньшая боковая сторона трапеции ABCD. Тогда точка M касания данной окружности с нижним основанием AD лежит на серединном перпендикуляре к основанию BC. Поэтому  AM = ^BC/₂ = ^x/₂,  CD = MD = a – ^x/₂.
  Пусть K – проекция вершины C на AD. Тогда  KD = a – x,  CK = x.  По теореме Пифагора  (a – ^x/₂)² = x² + (a – x)²,  откуда  x = ^4a/₇,  CD = a – ^x/₂ = ^5a/₇.

Ответ

^4a/₇, ^5a/₇.

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