Решение задачи о вертикальной линии симметрии с собеседования в Яндекс

Условие. Дан массив точек с целочисленными координатами (x, y). Определить, существует ли вертикальная прямая, делящая точки на 2 симметричных относительно этой прямой множества.

Пример 1:

Дано: [(1, 3), (3, 3), (2, 2), (2, 10), (0, 4), (4, 4)]

Ответ: true

Пример 2:

Дано: [(1, 4), (3, 3), (6, 2)]

Ответ: false

Решение. Данная задача может испугать своей "математичностью" — придется вспомнить школьную программу, а именно понятие двухмерной плоскости и координат. Также для решения поможет нарисовать систему координат на листочке, разбросать на ней точки и подумать, как бы проходила ось симметрии.

На что стоит обратить внимание:

1. Требуется найти вертикальную прямую, то есть по сути от нас требуют симметрию по оси Х;
2. Симметрия подразумевает, что у каждой точки есть пара, которая отстает на такое же расстояние от оси симметрии (по Х в этом случае), что и данная точка, только с другой стороны.

Таким образом, можно прикинуть алгоритм для решения задачи:

1. Найти Х координату оси симметрии. Можно догадаться, особенно из рисунка, что эта координата равна среднему значению Х координат всех точек множества.
2. Для каждой точки найти пару. Пройтись по списку точек и попробовать найти пару относительно оси симметрии для каждой из представленных в множестве. Напомню, что парой является точка, обладающая той же Y координатой (потому что симметрия вертикальная), а координата X отличается на два расстояния до оси симметрии.