основной форум
Список форумов algolist.manual.ru
Архив сообщений до 2004 года
Algolist: алгоритмы и методы программирования
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 

Задача "Изоляция"

 
Начать новую тему   Ответить на тему    Список форумов algolist.manual.ru -> Задачи
Предыдущая тема :: Следующая тема  
Автор Сообщение
Васёк



Зарегистрирован: 30.07.2004
Сообщения: 3

СообщениеДобавлено: Сб Июл 31, 2004 12:10 pm    Заголовок сообщения: Задача "Изоляция" Ответить с цитатой

http://www.lio.lv/olimps/uzdevumi.php?show=58
Время на тест: 2 сек

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

infile:
в первой строке дано нат. число N ( N <= 1000 ), далее идёт N строк по 3 числа - X, Y, R, каждое из которых не превосходит по модулю 1000.

outfile:
В единственной строке с точностью до двух знаков после запятой вывести длину плёнки.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
a_sergeyev



Зарегистрирован: 30.09.2003
Сообщения: 571
Откуда: СГАУ

СообщениеДобавлено: Сб Июл 31, 2004 12:30 pm    Заголовок сообщения: Ответить с цитатой

Это уже обсуждалось на Алгофоруме, кажется, никто ничего разумного не подсказал.
Ясно, что нужно построить оболочку, можешь попробовать усложненный алгоритм Грехема, но не знаю, насколько получится.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Васёк



Зарегистрирован: 30.07.2004
Сообщения: 3

СообщениеДобавлено: Сб Июл 31, 2004 12:52 pm    Заголовок сообщения: Ответить с цитатой

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

Допустим, что мы нашли выпуклую оболочку, но как тогда посчитать длину ( если все радиусы разные )?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
a_sergeyev



Зарегистрирован: 30.09.2003
Сообщения: 571
Откуда: СГАУ

СообщениеДобавлено: Сб Июл 31, 2004 2:18 pm    Заголовок сообщения: Ответить с цитатой

Временная сложность алгоритма Грехема O(n*log(n)), то есть по времени прокатит. Сложность будет в реализации.
Нет смысла добавлять какие-то точки, можно и так подсчитать длину. Если известна ломаная, как список вершин в порядке обхода, то это несложно сделать. Можно ведь рассчитать точки соприкосновения оболочки с цилиндрами (по 2 на цилиндр), если конечно не будет случая, когда один пленка касается одного цилиндра с разных сторон.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Васёк



Зарегистрирован: 30.07.2004
Сообщения: 3

СообщениеДобавлено: Сб Июл 31, 2004 2:33 pm    Заголовок сообщения: Ответить с цитатой

Такой случай вполне может быть - самый простой - треугольник ( три маленькие в вершинах, один большой в центре, большой настолько, что касается всех трёх сторон ).

Как определить прямые отрезки это я знаю ( расстояния между радиусами соседних целиндров ) Но как определить длину плёнки, где она соприкасается с окружностью, как найти эти самые точки?

Точки я имел ввиду добавить не для длины, а для нахождения оболочки - целиндры у нас окружности, поэтому просто воспользоваться координатами радиусов при её нахождении будет неправильно.

P.S. задача лежит в разделе не очень сложных, да и времени на неё даётся 2 сек, а такое время на этом сервере, обычно, даётся не просто так, то есть можно предположить, что сложность этой задачи либо O(N^2), либо O(N^2*logN) ... Второе вероятней... Да, и как работает этот алгоритм Грехема, где можно прочитать про него?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
a_sergeyev



Зарегистрирован: 30.09.2003
Сообщения: 571
Откуда: СГАУ

СообщениеДобавлено: Сб Июл 31, 2004 10:19 pm    Заголовок сообщения: Ответить с цитатой

Я читал про этот алгоритм в Кормене, "Алгоритмы: построение и анализ", в главе "Вычислительная геометрия". Наверняка и в сети есть множество источников.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов algolist.manual.ru -> Задачи Часовой пояс: GMT + 3
Страница 1 из 1

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах