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

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

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

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


Гость






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


Бывалый
***

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

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


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


Гость






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


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

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

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


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

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

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

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

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


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


Гость






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


Пионер
**

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

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


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


Пионер
**

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

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


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


Гость






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


Пионер
**

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

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


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

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

 

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