Лечебница Аркхем

Дано множество точек. Требуется провести минимальное количество прямых, чтобы любые две точки были разделены хотя бы одной прямой. Каждая прямая разбивает точки на два множества точек — с одной стороны от прямой, и с другой. Понятно, что в рамках задачи прямые, которые образуют одинаковые множества, лежат в одном классе эквивалентности. Научимся получать все возможные классы прямых. Переберем подмножество точек, которые будут лежать по одну сторону от прямой. Проверим, что их выпуклая оболочка не имеет общих точек с выпуклой оболочкой оставшихся точек. Теперь, для двух непересекающихся выпуклых оболочек нужно найти прямую, которая их разделяет — она будет представителем класса эквивалентности. Несложно доказать, что количество классов не превышает $$$n^2$$$.

Рассмотрим состояние, которое мы имеем после проведения нескольких прямых. Есть некоторые множества точек, которые еще не отделены друг от друга. Причем, если точки $$$a$$$ и $$$b$$$ не отделены, и точки $$$b$$$ и $$$c$$$ не отделены, не сложно заметить, что $$$a$$$ и $$$c$$$ тоже не отделены. Осталось реализовать аналог bfs-а по состояниям, где переходом будет добавление одной из прямых. При ограничении $$$n \le 12$$$, количество различных состояний оказывается порядка $$$140\,000$$$. Поэтому, данное решение укладывается в ограничение по времени.