E087. Построение выпуклой оболочки обходом Грэхэма

e-maxx algorithm оригинал: C/C++ #algorithm #emaxx #geometry #math

Static

Источник: e-maxx.ru/algo, страница PDF 249.

Даны N точек на плоскости. Построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, содержащий все эти точки. Мы рассмотрим метод Грэхэма (Graham) (предложен в 1972 г.) с улучшениями Эндрю (Andrew) (1979 г.). С его помощью можно построить выпуклую оболочку за время O (N log N) с использованием только операций сравнения, сложения и умножения. Алгоритм является асимптотически оптимальным (доказано, что не существует алгоритма с лучшей асимптотикой), хотя в некоторых задачах он неприемлем (в случае параллельной обработки или при online-обработке).

Описание

Алгоритм. Найдём самую левую и самую правую точки A и B (если таких точек несколько, то возьмём самую нижнюю среди левых, и самую верхнюю среди правых). Понятно, что и A, и B обязательно попадут в выпуклую оболочку. Далее, проведём через них прямую AB, разделив множество всех точек на верхнее и нижнее подмножества S1 и S2 (точки, лежащие на прямой, можно отнести к любому множеству - они всё равно не войдут в оболочку). Точки A и B отнесём к обоим множествам. Теперь построим для S1 верхнюю оболочку, а для S2 - нижнюю оболочку, и объединим их, получив ответ. Чтобы получить, скажем, верхнюю оболочку, нужно отсортировать все точки по абсциссе, затем пройтись по всем точкам, рассматривая на каждом шаге кроме самой точки две предыдущие точки, вошедшие в оболочку. Если текущая тройка точек образует не правый поворот (что легко проверить с помощью Ориентированной площади), то ближайшего соседа нужно удалить из оболочки. В конце концов, останутся только точки, входящие в выпуклую оболочку. Итак, алгоритм заключается в сортировке всех точек по абсциссе и двух (в худшем случае) обходах всех точек, т. е. требуемая асимптотика O (N log N) достигнута.

Реализация

struct pt {

double x, y;

};

bool cmp (pt a, pt b) {

return a.x < b.x || a.x == b.x && a.y < b.y;

}

bool cw (pt a, pt b, pt c) {

return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;

}

bool ccw (pt a, pt b, pt c) {

return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;

}

void convex_hull (vector<pt> & a) {

if (a.size() == 1)  return;

sort (a.begin(), a.end(), &cmp);

pt p1 = a[0], p2 = a.back();

vector<pt> up, down;

up.push_back (p1);

down.push_back (p1);

for (size_t i=1; i<a.size(); ++i) {

if (i==a.size()-1 || cw (p1, a[i], p2)) {

while (up.size()>=2 && !cw (up[up.size()-2], up[up.

size()-1], a[i]))

up.pop_back();

up.push_back (a[i]);

}

if (i==a.size()-1 || ccw (p1, a[i], p2)) {

while (down.size()>=2 && !ccw (down[down.size()-2],

down[down.size()-1], a[i]))

down.pop_back();

down.push_back (a[i]);

} }

a.clear();

for (size_t i=0; i<up.size(); ++i)

a.push_back (up[i]);

for (size_t i=down.size()-2; i>0; --i)

a.push_back (down[i]);

}

C# решение

auto-draft, проверить перед отправкой

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    bool cmp (pt a, pt b) {
            return a.x < b.x || a.x == b.x && a.y < b.y;
    }
    bool cw (pt a, pt b, pt c) {
            return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
    }
    bool ccw (pt a, pt b, pt c) {
            return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
    }
    void convex_hull (vector<pt> & a) {
            if (a.size() == 1)  return;
            sort (a.begin(), a.end(), &cmp);
            pt p1 = a[0],  p2 = a.back();
            vector<pt> up, down;
            up.push_back (p1);
            down.push_back (p1);
            for (size_t i=1; i<a.size(); ++i) {
                    if (i==a.size()-1 || cw (p1, a[i], p2)) {
                            while (up.size()>=2 && !cw (up[up.size()-2], up[up.
    size()-1], a[i]))
                                    up.pop_back();
                            up.push_back (a[i]);
                    }
                    if (i==a.size()-1 || ccw (p1, a[i], p2)) {
                            while (down.size()>=2 && !ccw (down[down.size()-2],
    down[down.size()-1], a[i]))
                                    down.pop_back();
                            down.push_back (a[i]);
                    }
            }
            a.clear();
            for (size_t i=0; i<up.size(); ++i)
                    a.push_back (up[i]);
            for (size_t i=down.size()-2; i>0; --i)
                    a.push_back (down[i]);
    }
}

C++ решение

сопоставлено/оригинал

struct pt {
        double x, y;
};
bool cmp (pt a, pt b) {
        return a.x < b.x || a.x == b.x && a.y < b.y;
}
bool cw (pt a, pt b, pt c) {
        return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
bool ccw (pt a, pt b, pt c) {
        return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
void convex_hull (vector<pt> & a) {
        if (a.size() == 1)  return;
        sort (a.begin(), a.end(), &cmp);
        pt p1 = a[0],  p2 = a.back();
        vector<pt> up, down;
        up.push_back (p1);
        down.push_back (p1);
        for (size_t i=1; i<a.size(); ++i) {
                if (i==a.size()-1 || cw (p1, a[i], p2)) {
                        while (up.size()>=2 && !cw (up[up.size()-2], up[up.
size()-1], a[i]))
                                up.pop_back();
                        up.push_back (a[i]);
                }
                if (i==a.size()-1 || ccw (p1, a[i], p2)) {
                        while (down.size()>=2 && !ccw (down[down.size()-2],
down[down.size()-1], a[i]))
                                down.pop_back();
                        down.push_back (a[i]);
                }
        }
        a.clear();
        for (size_t i=0; i<up.size(); ++i)
                a.push_back (up[i]);
        for (size_t i=down.size()-2; i>0; --i)
                a.push_back (down[i]);
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    boolean cmp (pt a, pt b) {
            return a.x < b.x || a.x == b.x && a.y < b.y;
    }
    boolean cw (pt a, pt b, pt c) {
            return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
    }
    boolean ccw (pt a, pt b, pt c) {
            return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
    }
    void convex_hull (vector<pt> & a) {
            if (a.size() == 1)  return;
            sort (a.begin(), a.end(), &cmp);
            pt p1 = a[0],  p2 = a.back();
            vector<pt> up, down;
            up.push_back (p1);
            down.push_back (p1);
            for (size_t i=1; i<a.size(); ++i) {
                    if (i==a.size()-1 || cw (p1, a[i], p2)) {
                            while (up.size()>=2 && !cw (up[up.size()-2], up[up.
    size()-1], a[i]))
                                    up.pop_back();
                            up.push_back (a[i]);
                    }
                    if (i==a.size()-1 || ccw (p1, a[i], p2)) {
                            while (down.size()>=2 && !ccw (down[down.size()-2],
    down[down.size()-1], a[i]))
                                    down.pop_back();
                            down.push_back (a[i]);
                    }
            }
            a.clear();
            for (size_t i=0; i<up.size(); ++i)
                    a.push_back (up[i]);
            for (size_t i=down.size()-2; i>0; --i)
                    a.push_back (down[i]);
    }
}

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.