Задача про деревья и треугольные заборы Опции

[Unconnected]

Привет всем. Мне нужно решить такую задачу:

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

Вводится информация о трех окружностях: каждая задается координатами центра и радиусом. Все числа целые, не превосходящие по модулю 1000, радиус – натуральное число. Клумбе соответствует первая окружность, вторая и третья окружности лежат внутри первой и соответствуют деревьям.

Если деревья невозможно оградить забором, не выходящим за границы клумбы, выведите impossible. Иначе в первую строку запишите possible, а в следующие – координаты вершин искомого треугольника. Если ответов несколько, выведите любой.

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

Сообщение отредактировано: Unconnected - 26.11.2009 15:16

[Shuruper]

Можно решить задачу с помощью графики или только в текстовом режиме?

[Unconnected]

Мм видимо только в текстовом.

[Archon]

Думаю, решить можно так:

1. Находим касательную к обоим деревьям (такую, чтобы оба дерева лежали по одну ее сторону). Таких касательных будет две. Берем одну из них.
2. Находим точки пересечения этой касательной с клумбой. Это точки А и B.
3. Находим касательную (не совпадающую с касательной АВ) от точки А к ближайшей окружности.
4. Находим касательную (не совпадающую с касательной АВ) от точки В к ближайшей окружности.
5. Находим их точку пересечения (точка С).
6. Если С лежит внутри клумбы, забор можно построить, иначе пробуем вторую касательную из пункта 1. Если и с той не получается, значит нельзя построить такой забор.

Для построения касательных можно адаптировать алгоритмы из начертательной геометрии: Построение сопряжений.

[Lapp]

Вот этот диалог:

Можно решить задачу с помощью графики или только в текстовом режиме?

Мм видимо только в текстовом.

- так и остался для меня загадкой, полной таинственного непостижимого смысла.. Что имелось в виду-то?..

Думаю, решить можно так:
...

Unconnected, чего молчишь - поймал топор-то?..
Или что-то неясно?..

[Unconnected]

- так и остался для меня загадкой, полной таинственного непостижимого смысла.. Что имелось в виду-то?.. blink.gif

Приоткрою завесу тайны: это значило, что графический режим использовать не надо, всё должно решаться на уровне математических вычислений:)


Archon, спасибо за алгоритм, наверное так это и должно решаться. Но как это делать, представляю достаточно туманно.

Если взять случай, когда деревья не срослись, то найти касательную будет просто. Найти - в моём понимании найти две её координаты, касания с обоими деревьями. Просто берем самую крайнюю точку от каждой окружности, координата которой меньше координаты центра (это всего лишь мои предположения)). А вот потом чего, я пока не знаю)

Сообщение отредактировано: Unconnected - 28.11.2009 23:22

[Archon]

А ссылку смотрел? А реализовать этот принцип программно тебе поможет аналитическая геометрия на плоскости.

Например:
Прямая задается уравнением A*x + B*y + C = 0, то есть три числа A, B, C однозначно определяют прямую. Для нахождения прямой по двум несовпадающим точкам используется уравнение: (y1 - y2)*x + (x2 - x1)*y + (x1*y2 - x2*y1) = 0. То есть A = y1 - y2, B = x2 - x1, C = x1*y2 - x2*y1.

Окружность можно задать в виде уравнения (x - x0)^2 + (y - y0)^2 = R^2, где (x0, y0) - центр окружности, R - ее радиус. Пересечение двух окружностей можно свести к задаче пересечения окружности и прямой вот так. Там же указано, как решить эту задачу.

На том же сайте можно найти алгоритм нахождения точки пересечения двух прямых, даже с примером на Си.

Начни написание программы с задания типов данных для окружностей, прямых и точек. Затем напиши функции для нахождения касательных и точек пересечения. Помочь с этим?

Сообщение отредактировано: Archon - 29.11.2009 13:22

[Unconnected]

Помочь с этим?

Пока что не нужно, сегодня, чуть позже, я попытаюсь сам это сделать, всю математику ты рассказал, спасибо:)