IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задача про деревья и треугольные заборы
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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

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

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

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


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

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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Антон

Репутация: -  0  +


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


--------------------
Я бы исправил мир, но Бог не дает мне исходников...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Вот этот диалог:
Цитата(Shuruper @ 26.11.2009 17:24) *
Можно решить задачу с помощью графики или только в текстовом режиме?
Цитата(Unconnected @ 26.11.2009 20:17) *
Мм видимо только в текстовом.
- так и остался для меня загадкой, полной таинственного непостижимого смысла.. Что имелось в виду-то?.. blink.gif

Цитата(Archon @ 27.11.2009 23:04) *
Думаю, решить можно так:
...
Unconnected, чего молчишь - поймал топор-то?.. smile.gif
Или что-то неясно?..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


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


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

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

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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

Например:
Прямая задается уравнением 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 -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:39
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name