Задачи на многоугольники¶
Очень часто геометрические задачи на контестах - это задачи на многоугольники. Некоторые из таких задач мы уже обсудили на предыдущих занятиях. Так мы уже обсудили задачу проверки многоугольника на выпуклость и научились находить площадь многоугольника. Напомним, что такое полярный угол.
Выпуклые оболочки¶
Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству
Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.
Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.
Дано множество точек, требуется построить его минимальную выпуклую оболочку :
Построение за $O(nh)$¶
Алгоритм Джарвиса(метод заворачивания подарка)¶
Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую оболочкуо, например обычно берут нижнюю и если таких несколько, то самую левую из них. Теперь давайте по одной набирать точки, как бы заворачивая нашу выпуклую оболочку(отсюда и название). Как же нам найти следующую точку в выпуклую оболочку, давайте пройдемся по точкам, которые мы еще не взяли в МВО и среди них выберем с минимальным полярным углом.
Корректность алгоритма легко доказывается по индукции, так как на первом шагу мы выбрали точку, точно лежащую в МВО, а на i, взяли такую точку, что все остальные лежат в нужной нам стороне.
Асимптотика : для каждой точки выпуклой оболочки мы из всех оставшихся точек будем искать оптимальную - что будет работать за h(размер выпуклой оболочки) * n
Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это¶
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);
Построение за $O(n \log n)$¶
Алгоритм Грэхема¶
Алгоритм Грэхема базируется на следующей идее: Давайте не искать следующую точку каждый раз, а сделаем так, чтобы у нас всегда была оптимальная точка и мы могли бы просто ее достать и проверить.
В прошлом алгоритме мы искали точку, оптимальную по полярному углу, тогда давайте сейчас сразу отсортируем точки по полярному углу и сразу возьмем две первые точки в МВО.
Теперь будем делать следующий алгоритм, пока все точки не будут просмотрены :
1) Возьмем первую из отсортированных точек.
2) Проверем последние три точки из взятых, если они образуют правый поворот, то удалим предпоследнюю точку
Сделать это можно, например, стеком. Код есть ниже.
Асимптотика : Мы просмотрим одну точку и либо удалим ее, либо оставим, то есть сам поиск МВО работает за линейное время, но мы еще делаем сортировку, а $\rightarrow$ алгоритм работает за $O(n\log(n))$, при этом его корректность вытекает из предыдущего алгоритма.
Красивая визуализация - https://visualgo.net/en/convexhull
красивое видео - https://www.youtube.com/watch?v=BTgjXwhoMuI .
struct Point {
int x, y;
};
Point operator -(Point a, Point b)
{
return {a.x - b.x, a.y - b.y};
}
int operator ^(Point a, Point b)
{
return a.x * b.y - b.x * a.y;
}
bool comp(Point a, Point b) {
if (((a - zero) ^ (b - zero)) == 0)
return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
return ((a - zero) ^ (b - zero)) > 0;
}
bool cw(Point a, Point b, Point c)
{
return (a - b) * (c - b) > 0;
}
bool ccw(Point a, Point b, Point c)
{
return (a - b) * (c - b) < 0;
}
int main()
{
sort(all(p2), comp);
vector<Point> s;
s.push_back(p[min_ind]);
for (int i = 0; i < n - 1; i++) {
if (p2[i].x == s[s.size() - 1].x && p2[i].y == s[s.size() - 1].y)
continue;
while (s.size() > 1 && (vect(s[s.size() - 1], s[s.size() - 2]) ^
vect(s[s.size() - 1], p2[i])) > 0)
s.pop_back();
s.push_back(p2[i]);
}
}
Алгоритм Эндрю¶
Алгоритм Эндрю опирается на то, что вещественные числа не точны и предлагает поменять компаратор и строить не одну выпуклую оболочку, а две :
Давайте выберем самую нижнюю и самую правую точку, затем отсортируем точки по самому простому из возможных компараторов, теперь будем строить две оболочки от самой правой точки и самой левой, в итоге мы получим верхнюю и нижнюю части выпуклой оболочки
bool comp(Point a, Point b) {
if(a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
int main() {
sort(all(p), comp);
vector<Point> up, down;
up.pb(p[0]);
down.pb(p[0]);
Point p1 = p[0], p2 = p.back();
for(int i = 1; i < n; i++) {
if (i == n - 1 || cw(p1, p[i], p2)) {
while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], p[i])) {
up.pop_back();
}
up.pb(p[i]);
}
if (i == n - 1 || ccw(p1, p[i], p2)) {
while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], p[i])) {
down.pop_back();
}
down.pb(p[i]);
}
}
}
Алгоритм Чена¶
Также существует алгоритм, объединяющий Джарвиса и Грэхема(Эндрю) и работающий за $O(n\log(h))$, но он разбираться не будет
Задачи¶
1) Базовые задачи - достаточно простые, например найти длину забора, чтобы ограничить многоугольник и подобные, но есть достаточно интересные задачи, в которых выпуклая оболочка неочевидна, например следующая : Даны $n$ пунктов в городе и $n$ почтальонов, для каждого пункта известно расстояние от почты $c_{i}$. Требуется каждому пункту доставить почту, $i$-ый почтальон просит $a_{i}$ монет, чтобы проснуться и $b_{i}$, чтобы проехать один километр, требуется для каждого пункта сказать, кто доставит почту наиболее выгодно. (Подсказка : $a_{i} + b_{i} * c_{j}$ - это прямая и стоимость доставки от $i$ почтальона к $j$ пункту).