Тoчки#359

Тoчки (Розбір)

Це класична задача комбінаторної геометрії, яка розв'язується рекурсивним розділенням.

Ключова ідея — знайти таку пару різнокольорових точок, з'єднання яких розбиває решту на дві частини, у кожній з яких порівну червоних і синіх. Тоді відрізок не перетинатиме жодного з відрізків, побудованих усередині частин, і задачу можна розв'язувати для кожної частини окремо.

Опишемо крок.

1. Опорна точка. Візьмемо точку з найменшою координатою (за рівності — з найменшою ). Вона гарантовано лежить на опуклій оболонці, тому всі інші точки видно з неї в межах кута .

2. Сортування за кутом. Відсортуємо решту точок за полярним кутом навколо . Оскільки жодні три точки не лежать на одній прямій, усі кути різні й порядок однозначний.

3. Пошук партнера. Підемо по відсортованому списку, ведучи баланс: додаємо одиницю за точку кольору, протилежного до , і віднімаємо за точку того самого кольору. Знайдемо першу точку протилежного кольору, перед якою баланс дорівнює нулю. З'єднаємо і .

Такий завжди існує: баланс змінюється на одиницю за крок, починається з нуля і в кінці (коли пройдено всі точки) дорівнює , бо точок протилежного до кольору рівно на одну більше серед решти. Отже, нуль перед точкою потрібного кольору обов'язково трапиться.

4. Рекурсія. Пряма ділить решту точок на дві групи — ті, що йдуть у сортуванні до , і ті, що після. За побудовою в кожній групі порівну червоних і синіх, тому запускаємо ту саму процедуру для кожної.

Відрізки не перетинаються: усі точки однієї групи лежать по один бік від , тому побудовані в різних групах відрізки не можуть перетнутися, а всередині групи це гарантує індукція.

Складність — \mathcal{O}(n^2 \log n): на кожному з рівнів рекурсії робиться сортування.

Порада щодо реалізації: порівнюйте кути векторним добутком у цілих числах, а не через atan2 — так уникнете похибок. Координати за модулем невеликі, тому добуток вміщується у 64-бітний тип.