Как определить вертикальную ось симметрии для списка точек?

Что проверяют

Умеете ли вы свести геометрическую задачу к хеш-множеству и заранее обсудить крайние случаи. Если ось существует, её положение определено однозначно, остаётся только проверить. Следом спрашивают про сложность, дубликаты и дробные координаты.

Как отвечать

Ключевое наблюдение: самая левая точка обязана отражаться в самую правую, поэтому ось может быть только x = (min_x + max_x) / 2.

• без дробей: храните не ось, а s = min_x + max_x. Отражение точки (x, y) это (s - x, y), всё остаётся целым, и не нужно сравнивать float;
• проверка: сложите точки в set кортежей и для каждой проверьте, что отражение тоже в множестве. Время O(n), память O(n);
• альтернатива без хешей: сгруппировать точки по y, отсортировать x в каждой группе и проверить, что x[i] + x[m-1-i] == s. Это O(n log n);
• крайние случаи: пустой список и одна точка, точки прямо на оси (отражаются сами в себя), дубликаты. Про дубликаты спросите: считать ли их одной точкой или требовать пару для каждой копии. Во втором случае вместо set нужен Counter.

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

Где спотыкаются

Ищут отражение в списке через in. Каждая проверка становится линейной, и решение незаметно превращается в O(n²).

Проверяют только x, забыв, что у пары должен совпадать и y. Тогда симметричными оказываются наборы, которые такими не являются.

Не проверяют свои примеры руками. Набор (1, 2), (3, 4), (5, 2), (5, 4) легко объявить симметричным, хотя ось здесь x = 3, и у точки (5, 4) нет пары (1, 4).