Алгоритм: наличие оси симметрии у конечного множества

[classman]

$(x_{1}, y_{1}), (x_{2}, y_{2}) ... (x_{n}, y_{n})$ - некие точки на плоскости.
Написать алгоритм, определяющий, обладает ли множество точек осью симметрии относительно оси, параллельной оси $y$. Должен работать по времени за $O(nlogn)$.

-- 12.07.2019, 22:28 --

Идея такая. Пройтись один раз по списку кортежей из точек и определить самую большую координату по модулю $(\max)$. Затем сортировать слиянием по параметру $(x\cdot \max + y)$. Затем копию списка сортировать по параметру $(x\cdot \max - y)$ и слить вторую половину копии в первую. Тогда получим список отсортированный по $x$, где первая половина, в случае равности $x$ -координат отсортирована по возрастанию $y$, вторая по убыванию. Тогда останется написать функцию, которая будет дергать по одному элементу сначала и с конца списка и проверять полусумму $x$ -координат с потенциальной осью симметрии. В случае равности - проверять на равность координаты $y$ .
Все бы очень хорошо, но получается довольно громоздко, а так не должно быть. Еще и затратно по памяти. Есть другие идеи?

[Dmitriy40]

Требование $O(n\log n)$ как бы намекает на сортировку.
Можно так: за линейное время найти минимум и максимум по $x$, вычислить их полусумму $s$, потом за $O(n \log n)$ отсортировать точки по координате $y$, потом за линейное время идти по массиву и проверять условие $s-x_a=x_b-s$ для точек $y_a=y_b,\,x_b>x_a$ (если точек с одинаковыми $y$ более двух, то усложнить условие или выкинуть совпадающие точки на этапе сортировки и тогда нахождение трёх точек с одинаковым $y$ сразу будет свидетельством несимметричности). Общая сложность при правильном выборе алгоритма сортировки $O(n+n\log n + n)=O(n\log n)$. Сортировки за $O(n \log n)$ есть и без дополнительной памяти (например Пирамидальная).

[realeugene]

classman в сообщении #1404822 писал(а):

Затем сортировать слиянием по параметру $(x\cdot \max + y)$

Плохая идея. Можно вылезти за диапазон чисел. Научитесь писать функции сравнения для кортежей.

[Евгений Машеров]

Найти среднее по y. Затем отсортировать по иксам, вторым ключом по абсолютным величинам отклонений $|y_i-\bar{y}|$ (при использовании устойчивой сортировки сперва по второму ключу, потом по первому, иначе лексикографическое сравнение пар ключей)
Если нет "дублей", то за один проход двигаемся шагом 2 и сравниваем пары объектов с номерами $2i, 2i+1$, если в паре не совпадают иксы или если при совпадении по иксам $y_{2i}\ne -y_{2i+1}$ - нет симметрии. Если возможны совпадающие и по x, и по y, чуть сложнее - считаем общее число совпадений в серии одинаковых иксов и абсолютных отлонений игреков, и сколько отклонений игреков положительных, сколько отрицательных. Если в серии совпадающих по иксам и абсолютным значениям отклонений нечётное число элементов - нет симметрии, если чётное, но положительных отклонений не столько, сколько отрицательных - нет симметрии.
Первый шаг O(n),как и последний. Сортировка $O(n\ln n)$

[B@R5uk]

Если у множества точек есть ось симметрии, то она проходит через центр масс. От этого и надо плясать. Например, упорядочить точки по расстоянию до центра масс. Дальнейшие действия зависят от того, нужна ли вам строгая симметрия (то есть для каждой точки есть точная зеркальная пара, либо же она лежит на оси), или у вас мягкая симметрия с возможными погрешностями.

[B@R5uk]

Если я не ошибаюсь, то оси собственного базиса тензора инерции тела всегда наплавлены вдоль осей симметрии или вдоль пересечения плоскостей симметрии, если таковые есть. Так что после подсчёта центра масс, можно найти тензор инерции, а затем его собственные оси. Для плоского тела это как раз будут оси симметрии, если таковые у тела имеются. Телом в данном случае будет набор точек одинаковой массы. Алгоритм будет вообще со сложностью $O(n)$ и будет находить и проверять вообще любое направление оси симметрии, а не только параллельное координатной оси исходной системы.

[grizzly]

Ещё некоторые точки могут находится прямо на оси симметрии (не уверен, что все комментаторы учли эту возможность, поэтому на всякий случай решил отдельно упомянуть о ней).

[B@R5uk]

grizzly, я про это писал выше.

А ещё, я тут подумал и вспомнил, что может быть так, что главные компоненты тензора инерции равны, и тогда выбрать какие-либо предпочтительные направления нельзя. Как правило это означает, что фигура имеет более, чем две оси симметрии. Как в этом случае алгоритму действовать, я не знаю.

[Sender]

B@R5uk в сообщении #1432988 писал(а):

Алгоритм будет вообще со сложностью $O(n)$

Вот тут как-то не очень понятно. Допустим, мы нашли прямую. Как за $O(n)$ установить, что она действительно является осью симметрии, с учётом того, что изначально массив точек никак не отсортирован?

[B@R5uk]

Sender, пожалуй, я поторопился с выводом. Проверка будет сложнее поиска.