Как построить выпуклую оболочку алгоритмом Эндрю (monotone chain) за O(n log n)?
Нужна выпуклая оболочка набора точек. Слышал про алгоритм Эндрю с сортировкой и построением верхней и нижней цепи. Можете дать корректную целочисленную реализацию и объяснить, почему получается O(n log n) и как обрабатывать точки на рёбрах?
2 ответа
Monotone chain Эндрю: сортируем точки по (x, затем y), строим нижнюю цепь слева направо и верхнюю справа налево, в каждой держим только левые повороты.
vector<P> convexHull(vector<P> p) {
int n = p.size(), k = 0;
if (n < 3) return p;
sort(p.begin(), p.end(), [](const P& a, const P& b){
return a.x != b.x ? a.x < b.x : a.y < b.y;
});
vector<P> h(2 * n);
// нижняя цепь
for (int i = 0; i < n; i++) {
while (k >= 2 && (h[k-1]-h[k-2]).cross(p[i]-h[k-2]) <= 0) k--;
h[k++] = p[i];
}
// верхняя цепь
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && (h[k-1]-h[k-2]).cross(p[i]-h[k-2]) <= 0) k--;
h[k++] = p[i];
}
h.resize(k - 1); // последняя точка дублирует первую
return h;
}
Идея: при добавлении точки, пока последний поворот не левый (cross <= 0), снимаем вершину со стека. Каждая точка добавляется и удаляется не более одного раза — поэтому сами проходы линейны, а доминирует сортировка: итого O(n log n). Память O(n). Результат — против часовой стрелки.
Про точки на рёбрах — это решает выбор оператора в cross(...) <= 0 vs < 0:
<= 0(как в коде) удаляет коллинеарные точки на рёбрах оболочки — остаются только вершины-углы. Так чаще нужно (минимальная оболочка).< 0сохраняет точки, лежащие точно на рёбрах. Нужно, если задача требует «все точки на границе оболочки».
Внимательно читай условие — это типичный источник WA на одном тесте. Ещё грабли: дубликаты точек и случай, когда все точки коллинеарны (оболочка вырождается в отрезок). Для надёжности удали дубликаты перед сортировкой. И помни про переполнение в cross — при больших координатах __int128. Альтернатива — алгоритм Грэхема (сортировка по полярному углу от нижней точки), та же асимптотика O(n log n), но monotone chain обычно проще и устойчивее.