Задачи на многоугольники

Очень часто геометрические задачи на контестах - это задачи на многоугольники. Некоторые из таких задач мы уже обсудили на предыдущих занятиях. Так мы уже обсудили задачу проверки многоугольника на выпуклость и научились находить площадь многоугольника. Напомним, что такое полярный угол.

alt text

Выпуклые оболочки

Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству

Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.

Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.

alt text

alt text

alt text

Дано множество точек, требуется построить его минимальную выпуклую оболочку :

Построение за $O(nh)$

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

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

alt text

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

Асимптотика : для каждой точки выпуклой оболочки мы из всех оставшихся точек будем искать оптимальную - что будет работать за h(размер выпуклой оболочки) * n

Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это

In [0]:
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) Проверем последние три точки из взятых, если они образуют правый поворот, то удалим предпоследнюю точку

Сделать это можно, например, стеком. Код есть ниже.

alt text

Асимптотика : Мы просмотрим одну точку и либо удалим ее, либо оставим, то есть сам поиск МВО работает за линейное время, но мы еще делаем сортировку, а $\rightarrow$ алгоритм работает за $O(n\log(n))$, при этом его корректность вытекает из предыдущего алгоритма.

Красивая визуализация - https://visualgo.net/en/convexhull

красивое видео - https://www.youtube.com/watch?v=BTgjXwhoMuI .

In [0]:
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]);
    }
}

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

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

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

In [0]:
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$ пункту).