Алгоритм Эндрю
Материал из Algocode wiki
Алгоритм Эндрю опирается на то, что вещественные числа не точны и предлагает поменять компаратор и строить не одну выпуклую оболочку, а две :
Давайте выберем самую нижнюю и самую правую точку, затем отсортируем точки по самому простому из возможных компараторов, теперь будем строить две оболочки от самой правой точки и самой левой, в итоге мы получим верхнюю и нижнюю части выпуклой оболочки
1 bool comp(Point a, Point b) {
2 if(a.x == b.x) {
3 return a.y < b.y;
4 }
5 return a.x < b.x;
6 }
7
8 int main() {
9 sort(all(p), comp);
10 vector<Point> up, down;
11 up.pb(p[0]);
12 down.pb(p[0]);
13 Point p1 = p[0], p2 = p.back();
14 for(int i = 1; i < n; i++) {
15 if (i == n - 1 || cw(p1, p[i], p2)) {
16 while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], p[i])) {
17 up.pop_back();
18 }
19 up.pb(p[i]);
20 }
21 if (i == n - 1 || ccw(p1, p[i], p2)) {
22 while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], p[i])) {
23 down.pop_back();
24 }
25 down.pb(p[i]);
26 }
27 }
28 }
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin