Алгоритм Джарвиса(Метод заворачивания подарка)
Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую оболочкуо, например обычно берут нижнюю и если таких несколько, то самую левую из них. Теперь давайте по одной набирать точки, как бы заворачивая нашу выпуклую оболочку(отсюда и название). Как же нам найти следующую точку в выпуклую оболочку, давайте пройдемся по точкам, которые мы еще не взяли в МВО и среди них выберем с минимальным полярным углом.
Корректность алгоритма легко доказывается по индукции, так как на первом шагу мы выбрали точку, точно лежащую в МВО, а на i, взяли такую точку, что все остальные лежат в нужной нам стороне.
Асимптотика : для каждой точки выпуклой оболочки мы из всех оставшихся точек будем искать оптимальную - что будет работать за h(размер выпуклой оболочки) $\cdot n$
Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это.
1 int base = 0;
2 for (int i = 1; i < n; i++) {
3 if (mas[i].y < mas[base].y) {
4 base = i;
5 }
6 else if (mas[i].y == mas[base].y && mas[i].x < mas[base].x) {
7 base = i;
8 }
9 }
10 convex_hull.push_back(base);
11 point first = mas[base];
12 point cur = first;
13 point prev = point(first.x - 1, first.y);
14 do {
15 double minCosAngle = 1e9; // чем больше угол, тем меньше его косинус
16 double maxLen = 1e9;
17 int next = -1;
18 for (int i = 0; i < n; i++) {
19 double curCosAngle = CosAngle(prev, cur, mas[i]);
20 if (Less(curCosAngle,minCosAngle)) {//если меньше сразу меняем
21 next = i;
22 minCosAngle = curCosAngle;
23 maxLen = dist(cur, mas[i]);
24 }
25 else if (Equal(curCosAngle, minCosAngle)) {// смотрим по длине
26 double curLen = dist(cur,mas[i]);
27 if (More(curLen,maxLen)) {
28 next = i;
29 maxLen = curLen;
30 }
31 }
32 }
33 prev = cur;
34 cur = mas[next];
35 convex_hull.push_back(next);
36 }
37 while (cur != first);
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin