Алгоритм Джарвиса(Метод заворачивания подарка): различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую о...»)
 
 
Строка 6: Строка 6:
  
 
Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это.
 
Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это.
 +
 +
<syntaxhighlight lang=C++ line=True>
 +
int base = 0;
 +
for (int i = 1; i < n; i++) {
 +
    if (mas[i].y < mas[base].y) {
 +
        base = i;
 +
    }
 +
    else if (mas[i].y == mas[base].y && mas[i].x < mas[base].x) {
 +
        base = i;
 +
    }
 +
}
 +
convex_hull.push_back(base);
 +
point first = mas[base];
 +
point cur = first;
 +
point prev = point(first.x - 1, first.y);
 +
do {
 +
    double minCosAngle = 1e9; // чем больше угол, тем меньше его косинус
 +
    double maxLen = 1e9;
 +
    int next = -1;
 +
    for (int i = 0; i < n; i++) {
 +
        double curCosAngle = CosAngle(prev, cur, mas[i]);
 +
        if (Less(curCosAngle,minCosAngle)) {//если меньше сразу меняем
 +
            next = i;
 +
            minCosAngle = curCosAngle;
 +
            maxLen = dist(cur, mas[i]);
 +
        }
 +
        else if (Equal(curCosAngle, minCosAngle)) {// смотрим по длине
 +
            double curLen = dist(cur,mas[i]);
 +
            if (More(curLen,maxLen)) {
 +
                next = i;
 +
                maxLen = curLen;
 +
            }
 +
        }
 +
    }
 +
    prev = cur;
 +
    cur = mas[next];
 +
    convex_hull.push_back(next);
 +
}
 +
while (cur != first);
 +
</syntaxhighlight>
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Текущая версия на 10:17, 26 февраля 2020

Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую оболочкуо, например обычно берут нижнюю и если таких несколько, то самую левую из них. Теперь давайте по одной набирать точки, как бы заворачивая нашу выпуклую оболочку(отсюда и название). Как же нам найти следующую точку в выпуклую оболочку, давайте пройдемся по точкам, которые мы еще не взяли в МВО и среди них выберем с минимальным полярным углом.

Корректность алгоритма легко доказывается по индукции, так как на первом шагу мы выбрали точку, точно лежащую в МВО, а на 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