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

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

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

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

Охват окружностью точек на плоскости
Здраствуйте. Пожалуйста помогите найти алгоритм задачи:
Дано массив точек на плоскости заданный координатами - [x1,y1],
[x2,y2], ... [xn,yn]. Необходимо найти окружность с минимальным радиусом (O[x,y] - координаты цетра окружности и r - длина радиуса), которая охватывала бы все точки массива. Перебор расстояний для каждой пары точеак не подходит.
Звранее благодарен.
  #2  
Старый 17.08.2010, 13:54
Местный

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

Посмотри, например, здесь.
Если нужна программа на С++, то она есть у меня.
  #3  
Старый 18.08.2010, 17:36
Новичок

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

Спасибо за помощь. Да это то что мне нужно. Сразу работу алгоритма не осилил. Если сможете то вышлите программу.
  #4  
Старый 18.08.2010, 17:48
Местный

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

Вот ссылка на программу.
  #5  
Старый 14.09.2010, 06:19
гость

 
Сообщений: n/a

как-то слабовато
во-первых хотелось бы за O( ln(n) )
во-вторых хотелось бы рассмотреть и более общий случай где точки это маленькие окружности
  #6  
Старый 14.09.2010, 06:32
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>хотелось бы за O( ln(n) )
Это хорошее желание
Однако нереальное, т.к. просто просмотр всех точек все равно займет O(n) времени
  #7  
Старый 14.09.2010, 10:56
Местный

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

> во-вторых хотелось бы рассмотреть и более общий случай где точки это маленькие окружности

Пожалуйста, рассматривай. Этот алгоритм легко обобщается на этот случай.
  #8  
Старый 14.09.2010, 13:19
Местный

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

Если радиус всех окружностей одинаковый ( R ), то охватывающая окружность будет иметь тот же центр, что и для точек, а радиус на R больше.
Вообще вместо точек можно брать любые фигуры, лишь бы вы умели строить охватывающую окружность для двух и трёх таких фигур.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
принадлежность точек плоскости гость Вычислительная геометрия 4 25.10.2009 19:07
На плоскости задано десять точек. гость Математические алгоритмы (другое) 2 20.03.2009 18:43
Две плоскости gamerfire Вычислительная геометрия 0 21.08.2008 23:10
Точки на плоскости. Wasya Вычислительная геометрия 4 20.02.2008 14:15
разбиение плоскости фигурами ASH Вычислительная геометрия 1 17.03.2007 15:13