Поиск ближайшей пары с помощью Divide и Conquer

Question

Мне в настоящее время назначено создание программы на C++ для поиска ближайшей пары точек в системе координат (x, y). Тем не менее, у меня много проблем, пытаясь понять одну вещь.

Каждый учебник/руководство, которое я прочитал о ближайшей проблеме пары, говорит мне сортировать множество точек по координатам Y, но я не понимаю, что это за точка? Может кто-нибудь объяснить мне, почему мы сортируем его по координатам Y и каково его использование? Я понимаю, что мы сортируем точки по X, чтобы получить L и X *, но я просто не понимаю, почему мы должны сортировать точки по координатам Y.

Answer 1

У вас нет, но тогда ваше время работы не улучшается над O (n). Все дело в том, чтобы вычислить как можно меньше - рассмотрев как можно меньше очков, игнорируя тех, кого вы знаете, не будет частью ответа. Сделайте это с помощью сортировки Y.

Вот довольно хорошее объяснение, которое я только гугла: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html