Есть несколько замечаний по алгоритму Quickhull.
1. Что будет если левая и нижняя точки совпадают? (Так же как и правая верхняя)
Можно упростить алгоритм найдя эти две точки, соединив их, затем поделить оставшиеся точки на 2 подмножества из разных полуплоскостей и для каждой из них решить рекурсивно.
2. При определении расстояния до самой удалённой точки от линии нет смысла делить на sqr(a^2+b^2), можно просто отнормировать вектор нормали (a,b). На самом деле можно обойтись и без этого, ведь в сравнении будут участвовать все точки с одним и тем же коэффициентом. (Единственная проблема может быть в разрядной сетке при представлении чисел).
3. Есть программа (по п.1), но она работает не на всех тестах из acmp.ru (задача 117, только она с дополнением, хотя дополнение прошло проверку на том же сайте - задача 370)
. На 4 тесте выдаёт неверный ответ. Соответственно, вопрос
Где можно найти набор тестов для проверки решения?
Стандартные варианты с расположением на одной линии, по периметру выпуклого многоугольника и немного произвольных отрабатываются нормально.
Если необходимо код могу выложить здесь же. (Хотя лучше сначала поправить ошибки
)
Линейный вид
