Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.01.2010, 12:34
Новичок

Отправить личное сообщение для Irjinn Посмотреть профиль Найти все сообщения от Irjinn
 
Регистрация: 16.01.2010
Сообщений: 1

Хитрый алгоритм
Добрый день!
Прошу прощение за бессодержательное название темы.

Суть задачи такова:
Имеется множество точек на плоскости J, построена выпуклая оболочка для этого множества. Как эффективно и просто в реализации построить окружность максимального радиуса, описанную вокруг трех точек из J, которая не пересекала бы выпуклую оболочку и не содержала бы внутри себя точек из J?

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

Возникает вопрос, как произвести предварительную триангуляцию, которая бы не пропустила оптимальное решение, т.е окружность максимального радиуса? Или хотябы оптимизировать перебор в случае с брутфорсом?

Голова соображает плохо, а времени осталось мало, так что, скорее всего, возьмусь за брутфорс. Может быть ктонибудь сталкивался с триангуляцией Делоне , а особенно, с ее реализацией для C++ (VS 2008)? Аналогично, боюсь не успею, согласно совету prografix, разобраться с диаграммой Вороного.

Буду благодарен за любую идею.

Последний раз редактировалось Irjinn, 17.01.2010 в 23:31.
  #2  
Старый 16.01.2010, 15:44
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Подобная задача описана у Препараты. Решается при помощи диаграммы Вороного.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача "Хитрый министр" гость Задачи 0 26.12.2009 15:29