Задача №402 «Коттеджный поселок» I acmp

В видео представлен подробный разбор задачи №402 «Коттеджный поселок» с платформы ACMP (сложность 75%, уровень регионального этапа ВсОШ). Рассмотрены два подхода к решению задачи: продвинутый алгоритм углового сканирования (Angular Sweep) со сложностью O(n² log n) и более простой метод перебора «чистых» пар точек со сложностью O(n³). Показано, как геометрическая задача о разделении точек прямой сводится к перебору пар и проверке принадлежности точки отрезку с использованием векторного и скалярного произведений. Разобраны важные аспекты реализации: хранение уникальных разбиений с помощью битовых масок в Python и полиномиального хэширования в C++, обработка коллинеарных точек, доказательство корректности алгоритмов. Приведены полные реализации на языках Python и C++, выполнено сравнение их преимуществ и недостатков. Материал предназначен для подготовки к олимпиадам по программированию и изучения методов вычислительной геометрии на плоскости.