![]() |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
![]() ![]() |
![]() |
Анка |
![]()
Сообщение
#1
|
Гость ![]() |
На плоскости задан набор окружностей(радиусами и координатими центра). Требуется написать программу, вычисляющую периметр и площадь выпуклой фигуры с минимальным периметром, которая содержит все заданные окружности.
Заранее спасиб всем, кто хоть что-нибудь подскажет. |
P@sh@ |
![]()
Сообщение
#2
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 180 Пол: Мужской Репутация: ![]() ![]() ![]() |
нифига себе задачка. ты хоть скажи, это уровень восьмого класса средней школы или последняя задача второго тура международной олимпиады по программированию?
|
Анка |
![]()
Сообщение
#3
|
Гость ![]() |
Уровнь, конечно, олимпиадный, но не международный. Подготовка...
Но какая разница? Решить все равно нужно. |
trminator |
![]()
Сообщение
#4
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
ИМХО это очень смахивает на задачу, в которой нужно построить многоугольник минимального периметра, но даны точки.
С тем, что многоугольник будет выпуклый, спорить, кажется не стоит. ИМХО нужно выбирать как бы "внешние" окружности. Что за "внешние" окружности можно объяснить так: возьмем и натянем вокруг этой группы окружностей резинку. Она, стянувшись, будет опираться как раз о "внешние" окружности. То есть нужно уметь находить эти самые "внешние" окружности. Можно попробовать поступать как в задаче с точками (могу ошибаться, глючить, но кажется, так): перебираем все пары окружностей. Для каждой из этих пар проводим к ним общую касательную так, чтобы обе окружности находились от нее по одну сторону. Проверяем, находятся ли по ту же сторону от этой касательной и остальные окружности (для каждой пары существуют две касательные, видимо, надо проверять обе. Хотя может, и без этого можно...) В результате получится многоугольник, выпуклый (по построению) и минимального периметра. -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
Анка |
![]()
Сообщение
#5
|
Гость ![]() |
Главное - построить касательную к двум окружностям. Но вот как это сделать(определить две точки, в которых она касается окружностей)?
|
pascal65536 |
![]()
Сообщение
#6
|
![]() Пионер ![]() ![]() Группа: Пользователи Сообщений: 62 Пол: Мужской Репутация: ![]() ![]() ![]() |
Может быть стоит найти уравнение касательной Y=aX+b для окружностей с координатами центра (X1,Y1) и (X2,Y2) и радиусами соответственно R1 и R2.
Уравнение окружности известно R^2=X^2+Y^2. Получится 2 прямых. Одну надо отбросить, так как она будет отсекать окружности от общей кучи окружностей. |
pascal65536 |
![]()
Сообщение
#7
|
![]() Пионер ![]() ![]() Группа: Пользователи Сообщений: 62 Пол: Мужской Репутация: ![]() ![]() ![]() |
Поправка: Уравнение окружности с центром в точке (X1,Y1) и радиусом R1 (X-x1)^2+(Y-Y1)^2=R^2.
Касательная к ней - первая производная. Угловой коэффициент - равен для обеих окружностей. |
Анка |
![]()
Сообщение
#8
|
Гость ![]() |
pascal65536, если искать производную уравнения окружности, которое, вообще говоря, раскладывается на две функции, получается довольно несимпатичное выражение. Но в него еще и надо подставить x(координата точки касания, которую пока найти не удалось).
|
pascal65536 |
![]()
Сообщение
#9
|
![]() Пионер ![]() ![]() Группа: Пользователи Сообщений: 62 Пол: Мужской Репутация: ![]() ![]() ![]() |
Предлагаю площадь фигуры определять методом Монте-Карло. Врёт, зараза, конечно.
|
![]() ![]() |
![]() |
Текстовая версия | 24.07.2025 23:45 |