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

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

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

 
 Ответить  Открыть новую тему 
> Площадь и периметр сложной фигуры
сообщение
Сообщение #1


Гость






На плоскости задан набор окружностей(радиусами и координатими центра). Требуется написать программу, вычисляющую периметр и площадь выпуклой фигуры с минимальным периметром, которая содержит все заданные окружности.
Заранее спасиб всем, кто хоть что-нибудь подскажет.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Бывалый
***

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

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


нифига себе задачка. ты хоть скажи, это уровень восьмого класса средней школы или последняя задача второго тура международной олимпиады по программированию?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Уровнь, конечно, олимпиадный, но не международный. Подготовка...
Но какая разница? Решить все равно нужно.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Четыре квадратика
****

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

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


ИМХО это очень смахивает на задачу, в которой нужно построить многоугольник минимального периметра, но даны точки.

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

ИМХО нужно выбирать как бы "внешние" окружности. Что за "внешние" окружности можно объяснить так: возьмем и натянем вокруг этой группы окружностей резинку. Она, стянувшись, будет опираться как раз о "внешние" окружности.

То есть нужно уметь находить эти самые "внешние" окружности. Можно попробовать поступать как в задаче с точками (могу ошибаться, глючить, но кажется, так): перебираем все пары окружностей. Для каждой из этих пар проводим к ним общую касательную так, чтобы обе окружности находились от нее по одну сторону. Проверяем, находятся ли по ту же сторону от этой касательной и остальные окружности (для каждой пары существуют две касательные, видимо, надо проверять обе. Хотя может, и без этого можно...)

В результате получится многоугольник, выпуклый (по построению) и минимального периметра.


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Главное - построить касательную к двум окружностям. Но вот как это сделать(определить две точки, в которых она касается окружностей)?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

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

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


Может быть стоит найти уравнение касательной Y=aX+b для окружностей с координатами центра (X1,Y1) и (X2,Y2) и радиусами соответственно R1 и R2.
Уравнение окружности известно R^2=X^2+Y^2. Получится 2 прямых. Одну надо отбросить, так как она будет отсекать окружности от общей кучи окружностей.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

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

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


Поправка: Уравнение окружности с центром в точке (X1,Y1) и радиусом R1 (X-x1)^2+(Y-Y1)^2=R^2.
Касательная к ней - первая производная. Угловой коэффициент - равен для обеих окружностей.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






pascal65536, если искать производную уравнения окружности, которое, вообще говоря, раскладывается на две функции, получается довольно несимпатичное выражение. Но в него еще и надо подставить x(координата точки касания, которую пока найти не удалось).
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

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

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


Предлагаю площадь фигуры определять методом Монте-Карло. Врёт, зараза, конечно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 




- Текстовая версия 21.11.2017 0:07
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"