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

Ориентация упорядоченной тройки точек на плоскости может быть:
⁃ Против часовой стрелки: математически ориентация является против часовой стрелки, если векторное произведение векторов AB и BC положительно.
⁃ По часовой стрелке: математически ориентация по часовой стрелке, если векторное произведение векторов AB и BC отрицательно.
⁃ Коллинеарность: Если ориентация коллинеарна, это означает, что точки A, B и C находятся на одной прямой. Математически ориентация коллинеарна, если векторное произведение векторов AB и BC равно нулю.

Сложность определение ориентации точек: O(1)

Соревнования пройдут в двух треках: алгоритмы и программирование роботов. Участвовать могут начинающие ИТ-специалисты и опытные разработчики.

В этом году ты сможешь:
— решать алгоритмические задачи в индивидуальном зачете;
— объединиться в команду с другими участниками и управлять роботом в лабиринте с помощью кода;
— попасть на офлайн шоу-финал в качестве участника или зрителя;
— побороться за призовой фонд 10 250 000 рублей.

Отборочные этапы состоятся онлайн, финал — 21 ноября в МТС Live Холл в Москве.

Регистрация открыта до 20 октября. Подай заявку прямо сейчас.

Алгоритм рекурсивного лабиринта — один из лучших примеров алгоритмов обратного отслеживания.

Лабиринт — это территория, окруженная стенами; между ними у нас есть путь от начальной точки до конечной позиции. Нам нужно начать с начальной точки и двигаться к конечной точке. Проблема в выборе пути.

Если мы обнаружим какой-либо тупик перед конечной точкой, нам придется вернуться назад и изменить направление. Направление движения — север, восток, запад и юг. Нам придется продолжать «двигаться и возвращаться», пока не достигнем финальной точки.

Вас ждет 4 недели практики, чтобы систематизировать знания и научиться решать задачи, которые встречаются на собеседованиях и в реальной работе.

Программа включает восемь ключевых тем: множества, словари, динамическое программирование и не только. Лекции и разборы будет вести Михаил Густокашин — директор Центра студенческих олимпиад ВШЭ и тренер чемпионов мира по программированию.

Топ-300 участников смогут пропустить контест при отборе на стажировку в Яндекс по направлениям бэкенд, фронтенд, мобилка и пройти пробное техническое собеседование. А еще лидеры рейтинга смогут получить персональные карьерные консультации.

Подать заявку можно до 29 сентября.

Разберём алгоритм Кнута–Морриса–Пратта (КМП): почему он работает за линейное время и как «переиспользует» уже найденные совпадения. Покажем, где наивный подход теряет секунды (и деньги), а КМП — нет.

После вебинара вы:
— понимаете префикс-функцию и логику «сдвигов»;
— умеете сравнить наивный поиск и КМП на реальных данных;
— знаете, как внедрить быстрый поиск в проде.

⏰ Урок пройдёт 24 сентября в 20:00 МСК в преддверие старта курса «Алгоритмы и структуры данных». Всем участникам — персональные условия обучения.

👉 Для участия зарегистрируйтесь: https://otus.pw/ny8hp/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

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

Алгоритм:
1. Сначала отсортируйте заданные точки по их полярным углам относительно опорной точки. Ориентиром может быть любая точка из набора.
2. Постройте путь: начиная с контрольной точки, посещайте точки в отсортированном порядке. Двигаясь от одной точки к другой, соединяйте их отрезками линий. Убедитесь, что путь не пересекает сам себя.
3. После посещения всех точек соедините последнюю точку с контрольной точкой, чтобы закрыть путь.

Сложность: O(n Log n), если мы используем алгоритм сортировки O(nLogn) для сортировки точек.