DBSCAN — Кластеризация на основе плотности
Density-Based Spatial Clustering of Applications with Noise — алгоритм кластеризации, объединяющий точки данных в группы на основе их плотности. Если точки находятся близко друг к другу, они считаются частью одного кластера. Если точка сильно удалена от других, она считается выбросом (шумом).
Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".
Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.
Density-Based Spatial Clustering of Applications with Noise — алгоритм кластеризации, объединяющий точки данных в группы на основе их плотности. Если точки находятся близко друг к другу, они считаются частью одного кластера. Если точка сильно удалена от других, она считается выбросом (шумом).
Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".
Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.
Поиск самой длинной общей подпоследовательности (Longest Common Subsequence)
Используется для нахождения наибольшей общей подпоследовательности между двумя строками или последовательностями.
Алгоритм:
1. Создание таблицы. Создаем таблицу размером
2. Итеративно проходимся по каждой ячейке таблицы слева направо и сверху вниз, сравнивая символы текущей позиции.
-Если символы совпадают, увеличиваем значение ячейки на 1 и переходим диагонально влево-вверх.
-Если символы не совпадают, выбираем максимальное значение из ячейки слева и сверху и записываем его в текущую ячейку.
3. Восстановление подпоследовательности. Начинаем с нижней правой ячейки таблицы и движемся влево или вверх, выбирая ячейки с максимальным значением. Если значения ячеек совпадают, добавляем символ к подпоследовательности и двигаемся диагонально влево-вверх. Повторяем этот процесс до тех пор, пока не достигнем левой верхней ячейки таблицы.
Сложность:
Используется для нахождения наибольшей общей подпоследовательности между двумя строками или последовательностями.
Алгоритм:
1. Создание таблицы. Создаем таблицу размером
(n+1) на (m+1), где n и m - длины строк или последовательностей.2. Итеративно проходимся по каждой ячейке таблицы слева направо и сверху вниз, сравнивая символы текущей позиции.
-Если символы совпадают, увеличиваем значение ячейки на 1 и переходим диагонально влево-вверх.
-Если символы не совпадают, выбираем максимальное значение из ячейки слева и сверху и записываем его в текущую ячейку.
3. Восстановление подпоследовательности. Начинаем с нижней правой ячейки таблицы и движемся влево или вверх, выбирая ячейки с максимальным значением. Если значения ячеек совпадают, добавляем символ к подпоследовательности и двигаемся диагонально влево-вверх. Повторяем этот процесс до тех пор, пока не достигнем левой верхней ячейки таблицы.
Сложность:
O(n*m)Поиск Фибоначчи
Метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.
Последовательность Фибоначчи начинается с чисел 0 и 1, а каждое следующее число равно сумме двух предыдущих чисел. Вот первые несколько чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.
Сложность:
Метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.
Последовательность Фибоначчи начинается с чисел 0 и 1, а каждое следующее число равно сумме двух предыдущих чисел. Вот первые несколько чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.
Сложность:
O(log n)Судоку
Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е.
⁃ Другой базовый случай — когда значение столбца равно
4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е.
5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е.
Сложность:
Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е.
i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.⁃ Другой базовый случай — когда значение столбца равно
N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е.
i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е.
i, j+1.Сложность:
O(9^(n*n)Проверка строки-палиндрома
Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «
Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.
Сложность:
Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «
abba» является палиндромом, потому что обратная сторона «abba» будет равна «abba».Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.
Сложность:
O(n)Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)
LPS — это самая длинная последовательность символов, которая является палиндромом.
Алгоритм поиска LPS:
1. Создаем матрицу dp размером
2. Заполняем главную диагональ матрицы значениями
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу
- Если символы на текущих позициях равны, увеличиваем значение
- Если символы не равны, выбираем максимальное значение из
4. Возвращаем значение
Сложность:
LPS — это самая длинная последовательность символов, которая является палиндромом.
Алгоритм поиска LPS:
1. Создаем матрицу dp размером
n x n, где n - длина исходной строки.2. Заполняем главную диагональ матрицы значениями
1, так как каждый символ сам по себе является палиндромом длины 1.3. Перебираем подпоследовательности строки разной длины и заполняем матрицу
dp с помощью следующих правил:- Если символы на текущих позициях равны, увеличиваем значение
dpij на 2 и переходим к следующим символам (i+1, j-1).- Если символы не равны, выбираем максимальное значение из
dpi+1j и dpij-1 и записываем его в dpij.4. Возвращаем значение
dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.Сложность:
O(n^2), где n - длина исходной строки.Ханойская башня
Головоломка, состоящая из трех стержней и набора дисков разного размера. Изначально диски располагаются на одном стержне в порядке убывания размера (больший диск находится ниже меньшего).
1. За один раз можно переместить только один диск.
2. Нельзя помещать больший диск на меньший.
Алгоритм:
1. Если на исходном стержне есть только один диск, переместите его на целевой стержень.
2. Если на исходном стержне есть больше одного диска, выполните следующие шаги:
- Переместите все диски, кроме самого большого, с исходного стержня на вспомогательный стержень.
- Переместите самый большой диск с исходного стержня на целевой стержень.
- Переместите все оставшиеся диски с вспомогательного стержня на целевой стержень.
Алгоритм:
Головоломка, состоящая из трех стержней и набора дисков разного размера. Изначально диски располагаются на одном стержне в порядке убывания размера (больший диск находится ниже меньшего).
1. За один раз можно переместить только один диск.
2. Нельзя помещать больший диск на меньший.
Алгоритм:
1. Если на исходном стержне есть только один диск, переместите его на целевой стержень.
2. Если на исходном стержне есть больше одного диска, выполните следующие шаги:
- Переместите все диски, кроме самого большого, с исходного стержня на вспомогательный стержень.
- Переместите самый большой диск с исходного стержня на целевой стержень.
- Переместите все оставшиеся диски с вспомогательного стержня на целевой стержень.
Алгоритм:
O(2^n), где n - количество дисков.Алгоритмы замены страниц в операционных системах (FIFO)
Цель алгоритма: уменьшение количества ошибок страниц.
Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.
FIFO это простейший алгоритм замены страниц. В этом алгоритме операционная система отслеживает все страницы в памяти в очереди, самая старая страница находится в начале очереди. Когда страницу необходимо заменить, страница в начале очереди выбирается для удаления.
Сложность:
Цель алгоритма: уменьшение количества ошибок страниц.
Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.
FIFO это простейший алгоритм замены страниц. В этом алгоритме операционная система отслеживает все страницы в памяти в очереди, самая старая страница находится в начале очереди. Когда страницу необходимо заменить, страница в начале очереди выбирается для удаления.
Сложность:
O(n), где n — количество страниц.Алгоритм оптимальной замены страниц
Цель алгоритма: уменьшение количества ошибок страниц. В этом алгоритме заменяются страницы, которые не будут использоваться в течение длительного времени в будущем.
Идея проста: для каждой ссылки мы делаем:
⁃ Если указанная страница уже существует, увеличьте количество обращений.
⁃ Если нет, найдите страницу, на которую никогда не будут ссылаться в будущем. Если такая страница существует, замените ее новой страницей. Если такой страницы не существует, найдите страницу, на которую в будущем будут чаще всего ссылаться. Замените эту страницу новой страницей.
Оптимальная замена страниц идеальна, но на практике невозможна, поскольку операционная система не может знать будущие запросы. Использование замены оптимальной страницы предназначено для установки эталона, позволяющего анализировать другие алгоритмы замены.
Сложность:
Цель алгоритма: уменьшение количества ошибок страниц. В этом алгоритме заменяются страницы, которые не будут использоваться в течение длительного времени в будущем.
Идея проста: для каждой ссылки мы делаем:
⁃ Если указанная страница уже существует, увеличьте количество обращений.
⁃ Если нет, найдите страницу, на которую никогда не будут ссылаться в будущем. Если такая страница существует, замените ее новой страницей. Если такой страницы не существует, найдите страницу, на которую в будущем будут чаще всего ссылаться. Замените эту страницу новой страницей.
Оптимальная замена страниц идеальна, но на практике невозможна, поскольку операционная система не может знать будущие запросы. Использование замены оптимальной страницы предназначено для установки эталона, позволяющего анализировать другие алгоритмы замены.
Сложность:
O(n × f), где n — количество страниц, а f — количество кадров.Least Recently Used алгоритм замены страниц
Наименее недавно использованный (LRU) — это алгоритм замены кэша, который заменяет кэш, когда пространство заполнено. Играет решающую роль, поскольку его можно использовать в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.
Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.
Наименее недавно использованный (LRU) — это алгоритм замены кэша, который заменяет кэш, когда пространство заполнено. Играет решающую роль, поскольку его можно использовать в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.
Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.
Most Recently Used алгоритм замены страниц
Используется в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.
MRU работает лучше всего среди всех алгоритмов замены страниц для особого типа последовательности запросов ссылок на страницы, когда одна и та же последовательность одних и тех же ссылок на страницы повторяется (в цикле).
Используется в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.
MRU работает лучше всего среди всех алгоритмов замены страниц для особого типа последовательности запросов ссылок на страницы, когда одна и та же последовательность одних и тех же ссылок на страницы повторяется (в цикле).
Матрица
Двумерная структура данных, состоящая из набора элементов, расположенных в строках и столбцах.
Каждый элемент матрицы идентифицируется индексами строки и столбца.
Преимущества:
⁃ Матрицы обеспечивают краткий и эффективный способ представления структурированных данных, особенно когда важны отношения между элементами.
⁃ Матрицы являются фундаментальными в линейной алгебре и используются в различных математических операциях.
⁃ При обработке изображений матрицы используются для представления значений пикселей, что позволяет выполнять преобразования и манипуляции.
Двумерная структура данных, состоящая из набора элементов, расположенных в строках и столбцах.
Каждый элемент матрицы идентифицируется индексами строки и столбца.
Преимущества:
⁃ Матрицы обеспечивают краткий и эффективный способ представления структурированных данных, особенно когда важны отношения между элементами.
⁃ Матрицы являются фундаментальными в линейной алгебре и используются в различных математических операциях.
⁃ При обработке изображений матрицы используются для представления значений пикселей, что позволяет выполнять преобразования и манипуляции.
Поворот элементов матрицы
Идея состоит в том, чтобы поочередно вращать все кольца элементов, начиная с самого дальнего.
Чтобы повернуть кольцо, нам нужно сделать следующее.
1. Переместить элементы верхнего ряда.
2. Переместить элементы последнего столбца.
3. Переместить элементы нижнего ряда.
4. Переместите элементы первого столбца.
Повторить вышеуказанные шаги для внутреннего кольца, пока оно есть.
Сложность:
Идея состоит в том, чтобы поочередно вращать все кольца элементов, начиная с самого дальнего.
Чтобы повернуть кольцо, нам нужно сделать следующее.
1. Переместить элементы верхнего ряда.
2. Переместить элементы последнего столбца.
3. Переместить элементы нижнего ряда.
4. Переместите элементы первого столбца.
Повторить вышеуказанные шаги для внутреннего кольца, пока оно есть.
Сложность:
O(m*n), где m — количество строк, а n — количество столбцов.Как узнать, является ли число степенью 2?
Чтобы определить, является ли число степенью 2, можно использовать следующий метод:
Проверьте, равно ли число 0. Если да, то 0 не является степенью 2.
Проверьте, является ли число положительным.
Если число положительное, используйте битовую операцию AND с числом (n - 1), где n - это число, которое вы проверяете.
Если результат операции AND равен 0, то число n является степенью 2.
Этот метод основан на том факте, что числа, являющиеся степенями 2, имеют только один бит, установленный в 1 в двоичном представлении (например, 2^3 = 8 в двоичном виде 1000, 2^4 = 16 в двоичном виде 10000). При вычитании единицы из таких чисел, все биты после первого устанавливаются в 1. Таким образом, если вы примените операцию AND к числу и его предшественнику, результат будет равен 0 только в том случае, если число является степенью 2.
Чтобы определить, является ли число степенью 2, можно использовать следующий метод:
Проверьте, равно ли число 0. Если да, то 0 не является степенью 2.
Проверьте, является ли число положительным.
Если число положительное, используйте битовую операцию AND с числом (n - 1), где n - это число, которое вы проверяете.
Если результат операции AND равен 0, то число n является степенью 2.
Этот метод основан на том факте, что числа, являющиеся степенями 2, имеют только один бит, установленный в 1 в двоичном представлении (например, 2^3 = 8 в двоичном виде 1000, 2^4 = 16 в двоичном виде 10000). При вычитании единицы из таких чисел, все биты после первого устанавливаются в 1. Таким образом, если вы примените операцию AND к числу и его предшественнику, результат будет равен 0 только в том случае, если число является степенью 2.
Кодирование длин серий (Run-Length Encoding, RLE)
Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.
Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.
Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность:
Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.
Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.
Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность:
O(n^2), где n - размер строки.Круговой сдвиг влево
Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.
При круговом сдвиге влево каждый элемент перемещается на одну позицию влево, а первый элемент переходит в последнюю позицию.
Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.
При круговом сдвиге влево каждый элемент перемещается на одну позицию влево, а первый элемент переходит в последнюю позицию.
Круговой сдвиг вправо
Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.
При круговом сдвиге вправо каждый элемент перемещается на одну позицию вправо, а последний элемент переходит в первую позицию.
Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.
При круговом сдвиге вправо каждый элемент перемещается на одну позицию вправо, а последний элемент переходит в первую позицию.
Ближайшая пара точек с использованием алгоритма «Разделяй и властвуй»
Алгоритм, используемый для поиска двух ближайших друг к другу точек в наборе точек двумерного пространства. Другими словами, он вычисляет минимальное расстояние между любыми двумя точками в заданном наборе.
Алгоритм:
1. Найдите среднюю точку, которая равна
2. Разделите массив на две половины: от
3. Рекурсивно находим минимальные расстояния в обеих половинах, получая
4. Пусть
5. Создайте массив «полосы», содержащий точки ближе, чем
6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.
Сложность:
Алгоритм, используемый для поиска двух ближайших друг к другу точек в наборе точек двумерного пространства. Другими словами, он вычисляет минимальное расстояние между любыми двумя точками в заданном наборе.
Алгоритм:
1. Найдите среднюю точку, которая равна
P[n/2].2. Разделите массив на две половины: от
P[0] до P[n/2] и от P[n/2+1] до P[n-1].3. Рекурсивно находим минимальные расстояния в обеих половинах, получая
dl и dr.4. Пусть
d будет минимумом dl и dr.5. Создайте массив «полосы», содержащий точки ближе, чем
d к средней вертикальной линии, и отсортируйте его по координатам y.6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.
Сложность:
O(n (Logn)^2)Проверить, находится ли данная точка внутри или снаружи многоугольника?
Алгоритм предполагает подсчет количества раз, когда луч, идущий из точки, пересекает края многоугольника. Если количество пересечений нечетное, точка находится внутри многоугольника; если оно четное, то точка находится снаружи.
Сложность:
Алгоритм предполагает подсчет количества раз, когда луч, идущий из точки, пересекает края многоугольника. Если количество пересечений нечетное, точка находится внутри многоугольника; если оно четное, то точка находится снаружи.
Сложность:
O(N)Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?
Алгоритм:
1. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.
2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.
3. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении по часовой стрелке. Сохраните их в векторе.
4. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении против часовой стрелки. Сохраните эти точки в векторе.
5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».
6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.
Сложность:
Алгоритм:
1. Отсортируйте данные точки вместе с точкой запроса в порядке возрастания их значений по абсциссе. Если значения абсцисс любых двух точек одинаковы, отсортируйте их по значению ординаты.
2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.
3. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении по часовой стрелке. Сохраните их в векторе.
4. Переберите все точки и найдите те, которые образуют выпуклый многоугольник, находящийся между начальной и конечной точками в направлении против часовой стрелки. Сохраните эти точки в векторе.
5. Проверьте, существует ли точка запроса в векторе, то она находится вне выпуклой оболочки. Поэтому верните «Нет».
6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.
Сложность:
O(N * log(N))