1
Одной из наиболее известных задач на геометрию - задача на построение выпуклой оболочки(ссылка на задачу внизу). Кто-то делает его алгоритмом Джарвиса за квадрат, кто-то - обычным алгоритмом Грэхема за 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
