234
правки
Изменения
→Псевдокод
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество. <tex>quick_hull()</tex> - рекурсивная функция, находящая оболочку подмножества <tex>S</tex>. В реализации в конце каждого подмножества находятся эл-ты, точно не принадлежащие оболочке.
QuickHull(S)
find i such that S[i] has the highest x-coordinate and lowest y-coordinate
swap(S[1], S[i])
find i such that S[i] has the lowest x-coordinate and lowest y-coordinate
swap(S[n], S[i])
k = partition1(S) // разбиваем на те эл-ты, которые лежат над прямой и на остальные
a = quick_hull(S, 1, k)
b = quick_hull(S, k + 1, n);
swap(S[a..k], S[k + 1, b])
return start + (a - 1) + (b - k - 1)
quick_hull(S, start, end)
find i such that S[i], S[start], S[end] has maximum value
(a, b) = partition2(S, start, end, S[i]) //свапаем эл-ты S так, чтобы сначала были все эл-ты над прямой S[start]S[i], потом S[i]S[end], потом все остальное
c = quick_hull(S, start, a)
d = quick_hull(S, a + 1, b)
swap(S[c..a], S[a + 1..d])
return start + (a - c) + (d - b)
== Сложность ==
