Перейти к содержимому


Выпуклая оболочка Грэхема-Эндрю


В теме одно сообщение

#1 LVP

    Продвинутый пользователь

  • Администраторы
  • 183 сообщений
  • ГородВитебск

Отправлено 14 October 2020 - 11:00

Выпуклая оболочка Грэхема-Эндрю (от Рубиша Артура)

Одной из наиболее известных задач на геометрию - задача на построение выпуклой оболочки(ссылка на задачу внизу). Кто-то делает его алгоритмом Джарвиса за квадрат, кто-то - обычным алгоритмом Грэхема за n log n, но с использованием вещественных чисел.

Однако всё же есть несколько способов обойтись без ошибки по времени и вещественных чисел. Одним из них является алгоритм Грэхема-Эндрю. Алгоритм является оптимальным и использует только сложение, умножение и вычитание.

Суть алгоритма довольно несложная, если вы хорошо понимаете алгоритм Грэхема. Давайте найдём самую левую нижнюю и самую правую верхнюю точки из данных нам. Пусть это будут точки А и В соответственно. Дальше мы проведём прямую через эти точки. Так, мы разделили прямую на две части - верхнюю и нижнюю(Точки на этой прямой, кроме А и В, мы не учитываем ни в какую из частей. Сами же точки А и В войдут в обе части).Дальше мы сортируем все точки по абсциссе, а при их равенстве - по ординате. Всё, что нам осталось сделать - использовать алгоритм Грэхема для построения сначала верхней, а затем и нижней части оболочки.

Код(для задачи, указанной ниже).

#include <bits/stdc++.h>
#define ld long double
#define int long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
using namespace std;
int32_t main ()
{
    ///Алгоритм Грэхема-Эндрю, написан и объяснён _GreatArthur_
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int copy = n;
    long double x[n], y[n];
    ///Используем map для удаления одинаковых точек.
    map < pair < ld, ld >, int > mp;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        mp[{x[i], y[i]}]++;
        if (mp[{x[i], y[i]}] > 1)
        {
            i--;
            n--;
        }
    }
    ///Отдельно проверяем частный случай.
    if (n == 1)
    {
        cout << 1 << endl << x[0] << ' ' << y[0];
        return 0;
    }
    ///Находим номера точек А и В.
    int numA = 0, numB = 0;
    for (int i = 0; i < n; i++)
    {
        if (x[numA] > x[i] || (x[numA] == x[i] && y[numA] > y[i]))
        numA = i;
        if (x[numB] < x[i] || (x[numB] == x[i] && y[numB] < y[i]))
        numB = i;
    }
    ///Создаём два множества для верхней и нижней части оболочки.
    vector < int > up, down;
    up.pb(numA);
    down.pb(numA);
    ///Сортируем точки по абсциссе(v[i].F), а при их равенстве - по ординате(v[i].S.F). Чтобы понять номер точек после сортировки, также храним их номер(v[i].S.S).
    vector < pair < int, pair < int, int > > > v;
    for (int i = 0; i < n; i++)
        v.pb({x[i], {y[i], i}});
    sort(v.begin(), v.end());
    int ii = 0;
    ///Ищем верхнюю часть оболочки.
    do
    {
        ii++;
        if ((x[v[ii].S.S] - x[numA]) * (y[numB] - y[numA]) - (y[v[ii].S.S] - y[numA]) * (x[numB] - x[numA]) <= 0 && v[ii].S.S != numB) continue;
        ///Для каждой точки мы проверяем, сверху ли она или её номер - numB.Если да, то мы делаем алгоритм ниже, иначе - просто игнорируем её.
        while (up.size() > 1 && (x[v[ii].S.S] - x[up[up.size() - 2]]) * (y[up[up.size() - 1]] - y[up[up.size() - 2]]) - (y[v[ii].S.S] - y[up[up.size() - 2]]) * (x[up[up.size() - 1]] - x[up[up.size() - 2]]) >= 0)
            up.pop_back();
        up.pb(v[ii].S.S);
    }
    while (ii < v.size() - 1);
    ii = 0;
    ///Ищем нижнюю часть оболочки.
    do
    {
        ii++;
        if ((x[v[ii].S.S] - x[numA]) * (y[numB] - y[numA]) - (y[v[ii].S.S] - y[numA]) * (x[numB] - x[numA]) >= 0 && v[ii].S.S != numB) continue;
        ///Для каждой точки мы проверяем, снизу ли она или её номер - numB.Если да, то мы делаем алгоритм ниже, иначе - просто игнорируем её.
        while (down.size() > 1 && (x[v[ii].S.S] - x[down[down.size() - 2]]) * (y[down[down.size() - 1]] - y[down[down.size() - 2]]) - (y[v[ii].S.S] - y[down[down.size() - 2]]) * (x[down[down.size() - 1]] - x[down[down.size() - 2]]) <= 0)
            down.pop_back();
        down.pb(v[ii].S.S);
    }
    while (ii < v.size() - 1);
    ///Выводим оболочку.
    cout << up.size() + down.size() - 2 << endl;
    if (copy % 2 == 0)
    {
        for (int i = 0; i < up.size(); i++)
            cout << x[up[i]] << ' ' << y[up[i]] << endl;
        for (int i = down.size() - 2; i >= 1; i--)
            cout << x[down[i]] << ' ' << y[down[i]] << endl;
    }
    else
    {
        for (int i = 1;i <= down.size() - 2; i++)
            cout << x[down[i]] << ' ' << y[down[i]] << endl;
        for (int i = up.size() - 1;i >= 0;i--)
            cout << x[up[i]] << ' ' << y[up[i]] << endl;
    }
    return 0;
}


Сдать задачу:

https://informatics....hapterid=1877#1

Сообщение отредактировал LVP: 17 October 2020 - 08:04

Виктория Павловна

#2 Степа

    Новичок

  • Пользователи
  • Pip
  • 1 сообщений
  • ГородВитебск

Отправлено 17 October 2020 - 06:59

Рубиш Артур проносит свои глубочайшие извинения и просит в поиске точек a и b искать левую нижнюю и правую верхнюю точки.





Количество пользователей, читающих эту тему: 2

0 пользователей, 2 гостей, 0 анононимных