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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.01.2011, 23:59
kon kon вне форума
Новичок

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

Построение выпуклой оболочки (модификация Quickhull)
Есть несколько замечаний по алгоритму Quickhull.

1. Что будет если левая и нижняя точки совпадают? (Так же как и правая верхняя)
Можно упростить алгоритм найдя эти две точки, соединив их, затем поделить оставшиеся точки на 2 подмножества из разных полуплоскостей и для каждой из них решить рекурсивно.

2. При определении расстояния до самой удалённой точки от линии нет смысла делить на sqr(a^2+b^2), можно просто отнормировать вектор нормали (a,b). На самом деле можно обойтись и без этого, ведь в сравнении будут участвовать все точки с одним и тем же коэффициентом. (Единственная проблема может быть в разрядной сетке при представлении чисел).

3. Есть программа (по п.1), но она работает не на всех тестах из acmp.ru (задача 117, только она с дополнением, хотя дополнение прошло проверку на том же сайте - задача 370) . На 4 тесте выдаёт неверный ответ. Соответственно, вопрос
Где можно найти набор тестов для проверки решения?
Стандартные варианты с расположением на одной линии, по периметру выпуклого многоугольника и немного произвольных отрабатываются нормально.

Если необходимо код могу выложить здесь же. (Хотя лучше сначала поправить ошибки )
  #2  
Старый 13.01.2011, 04:46
Пользователь

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

1) Тогда теряется сок как раз от того, что мы изначально отбрасываем ту часть точек, которая внутри четырехугольника.
2) Если ты точно уверен, что это константа, то делить на нее перед сравнением действительно не нужно.
3) Если есть вопросы по коду, то его разумно выложить. Тесты - рандом на больших количествах, плюс учет целочисленного переполения.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Модификация игры Ним OwnYou Задачи 15 14.03.2011 19:44
метода выпуклых оболочек QuickHull ciaonataha Вычислительная геометрия 14 23.07.2009 17:55
Построение невыпуклой оболочки. AndreyGL/D3D Вычислительная геометрия 13 06.04.2009 23:20
Принадлежность точки выпуклой оболочки 3d vladScr Вычислительная геометрия 6 15.05.2008 13:17
построение выпуклой поверхности в пространстве pjr Вычислительная геометрия 2 10.11.2006 17:03