Алгоритм Грэхема: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Алгоритм Грэхема базируется на следующей идее: Давайте не искать следующую точку каждый...») |
|||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 39: | Строка 39: | ||
bool cw(Point a, Point b, Point c) | bool cw(Point a, Point b, Point c) | ||
{ | { | ||
− | return (a - b) | + | return (a - b) ^ (c - b) > 0; |
} | } | ||
bool ccw(Point a, Point b, Point c) | bool ccw(Point a, Point b, Point c) | ||
{ | { | ||
− | return (a - b) | + | return (a - b) ^ (c - b) < 0; |
} | } | ||
Строка 62: | Строка 62: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 17:40, 27 февраля 2021
Алгоритм Грэхема базируется на следующей идее: Давайте не искать следующую точку каждый раз, а сделаем так, чтобы у нас всегда была оптимальная точка и мы могли бы просто ее достать и проверить.
В прошлом алгоритме мы искали точку, оптимальную по полярному углу, тогда давайте сейчас сразу отсортируем точки по полярному углу и сразу возьмем две первые точки в МВО.
Теперь будем делать следующий алгоритм, пока все точки не будут просмотрены :
1) Возьмем первую из отсортированных точек.
2) Проверем последние три точки из взятых, если они образуют правый поворот, то удалим предпоследнюю точку
Сделать это можно, например, стеком. Код есть ниже.
Асимптотика : Мы просмотрим одну точку и либо удалим ее, либо оставим, то есть сам поиск МВО работает за линейное время, но мы еще делаем сортировку, а $\rightarrow$ алгоритм работает за $O(n\log(n))$, при этом его корректность вытекает из предыдущего алгоритма.
Красивая визуализация - https://visualgo.net/en/convexhull
красивое видео - https://www.youtube.com/watch?v=BTgjXwhoMuI
1 struct Point {
2 int x, y;
3 };
4
5 Point operator -(Point a, Point b)
6 {
7 return {a.x - b.x, a.y - b.y};
8 }
9
10 int operator * (Point a, Point b)
11 {
12 return a.x * b.x + b.y * a.y;
13 }
14
15 int operator ^(Point a, Point b)
16 {
17 return a.x * b.y - b.x * a.y;
18 }
19
20 bool cw(Point a, Point b, Point c)
21 {
22 return (a - b) ^ (c - b) > 0;
23 }
24
25 bool ccw(Point a, Point b, Point c)
26 {
27 return (a - b) ^ (c - b) < 0;
28 }
29
30 int main()
31 {
32 sort(all(p2), comp);
33 vector<Point> s;
34 s.push_back(p[min_ind]);
35 for (int i = 0; i < n - 1; i++) {
36 if (p2[i].x == s[s.size() - 1].x && p2[i].y == s[s.size() - 1].y)
37 continue;
38 while (s.size() > 1 && (vect(s[s.size() - 1], s[s.size() - 2]) ^
39 vect(s[s.size() - 1], p2[i])) > 0)
40 s.pop_back();
41 s.push_back(p2[i]);
42 }
43 }
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin