Алгоритм Эндрю

Алгоритм Эндрю опирается на то, что вещественные числа не точны и предлагает поменять компаратор и строить не одну выпуклую оболочку, а две :

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

 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