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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 31.08.2009, 17:03
гость

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

Наиболее удаленные точки
Здравствуйте!
Задача - дано множество точек на плоскости. Нужно найти 2 наиболее удаленные друг от друга точки. Конечно не за O(N^2), а за O(N*log(N)). Я просто слышал что ее можно решить за такое время, но вот сам алгоритм чего то не нашел. Вроде как есть даже два алгоритма, 1 это построить выпуклую оболочку и там как то за линейное время найти самые удаленные точки 2, но вот как!?. А другой вроде разделяй и властвуй, но про него я вообще ничего не слышал.
  #2  
Старый 31.08.2009, 17:12
Местный

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

Сообщение от гость Посмотреть сообщение
1 это построить выпуклую оболочку и там как то за линейное время найти самые удаленные точки 2, но вот как!?.
Этот алгоритм описан в книге Препарата, Шеймос "Вычислительная геометрия: Введение" пункт 4.2.3.
  #3  
Старый 31.08.2009, 17:14
MBo MBo вне форума
Местный

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

с помощью Rotating calipers это можно сделать
  #4  
Старый 01.09.2009, 15:49
Пользователь

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

какое количество памяти можно использовать?
  #5  
Старый 02.09.2009, 13:29
гость

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

А бывают для разных обьемов памяти?
  #6  
Старый 02.09.2009, 16:19
Местный

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

Сообщение от Parabol
какое количество памяти можно использовать?
Никаких новых массивов. Только несколько переменных.
  #7  
Старый 03.09.2009, 09:45
Пользователь

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

если пользоваться "разделяй и властвуй" так нужно еще О(n) памяти.
ну а если разрешено добавить только O(1) памяти, так надо подумать...
  #8  
Старый 03.09.2009, 14:25
Местный

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

Точнее для построения выпуклой оболочки память О(n) понадобится и время O(N*log(N)). Зато для полученного многоугольника максимальный или минимальный диаметр считается без дополнительных массивов и за время О(n).
А о чём думать? Разве есть варианты?
  #9  
Старый 03.09.2009, 15:51
Пользователь

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

увы нету (я такое еще не учил), но советую попробовать очень полезную функцию
f: гугл---> википедия ---> книги
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Точки на костях гость Задачи 5 21.03.2011 18:35
точки ilyitch Вычислительная геометрия 1 03.09.2009 15:18
Точки и отрезки Miss K Сортировка и поиск 4 03.09.2009 01:41
Расположение точки и треугольника С++ гость Математические алгоритмы 1 05.06.2008 06:28
Точки на плоскости. Wasya Вычислительная геометрия 4 20.02.2008 14:15