Сортировка 2d точек на расстоянии от начала координат

Question

Мне нужно написать код ac, который сортирует случайное число из 2d точек от точки, которая находится ближе всего к , к месту происхождения, которое имеет наибольшее расстояние от начала координат. Поскольку Мне нужно иметь временную сложность n * log (n), где n - количество точек, которые мы получаем от пользователя Im, думающего об использовании метода сортировки кучи. Единственная проблема заключается в нахождении ближайшей пары к расстоянию на основе уравнения расстояние между (x, y и (0,0)), которое представляет собой sqrt ((x^2) + (y^2) и реализует это уравнение для метода сортировки, который я использую. Просто найдите некоторые подсказки или любые предложения о том, как я буду продолжать отсюда, поэтому я буду признателен за любой вопрос совет

Answer 1

Любой хороший алгоритм сортировки сравнения будет работать в O (n log n). Для эффективности вы хотите, чтобы компаратор работал как можно быстрее. Одна мысль: сравните x^2+y^2, а не фактическое расстояние. Другое: вычислять это количество только один раз для каждой точки и кэшировать его в объекте точки или в другом месте, а не пересчитывать для каждого сравнения.

Answer 2

Heap рода Решение:

1.Create макс кучи расстояния каждой точки от происхождения.

2.показать, если вы реализуете кучу по массиву, тогда просто создайте еще один фиктивный массив, который будет содержать индекс этой точки.

3. просто применяйте обычную сортировку кучи &, когда вы выполняете обмен между индексами, а затем заменяете одинаковый индекс в фиктивном массиве.

lets say my input from user is following point  
1,0 
8,6 
4,4 
6,0 

так что мое расстояние массив будет содержать расстояние

1,10,sqrt(32),6 

мой фиктивный массив будет содержать нормальный индекс каждой точки

1,2,3,4 

Теперь создать максимальную кучу после тару это ваш массив будет 10,6,sqrt(32),1 поэтому в то время ваш фиктивный массив будет выглядеть как 2,4,3,1. Применит теперь кучу сортировать 10 поменяется с 1, а также 2 будет быть своп с 1 в фиктивной массиве & так далее ......

Благодаря этому в фиктивном массиве вы получите весь индекс точки, которая ближайший от источника до самого дальнего от источника

скажите мне, есть ли что-либо, что вы не поняли.