Re: Сортировка комплексных чисел?

From

Sergey Andrianov (2:5020/1507.400)

To

Evgenij M. Baldin

Date

2002-08-10T00:00:40Z

Area

RU.ALGORITHMS

Здравствуй, Evgenij!

Однажды 08-Aug-02  в 13:26   Evgenij M. Baldin (via gate)
написал       All    по поводу
-=-   Сортировка  комплексных  чисел?  -=-

EMB> Задача: есть набор пар чисел, есть каким-то образом полученная пара - как 
EMB> в имеющемся наборе максимально быстро, кроме банального перебора найти 
EMB> ближайшее?

EMB> Есть набор (a_1,b_1)....(a_n,b_n) n порядка 20тыс
EMB> Есть (a,b)
EMB> Надо найти такое i, где \sqrt{(a_i-a)^2+(b_i-b)^2} -> min
 
EMB> Сейчас просто тупо перебираю, но слишком долго получается :(

   Для начала ищи минимум не корня из суммы квадратов, а самой суммы квадратов. В зависимости от компилятора может оказаться полезным заменить a^2 на a*a. 
   А вообще-то если поиск предполагается делать однократно, то, пожалуй, и все. А если допустимо потратить некоторый ресурс заранее (времени и памяти), а потом искать многократно - то можно придумать массу различных вариантов, например, покрыть область равномерной сеткой (ведь задача аналогична находжению точки на плоскости ближайшей к данной) и для каждой клетки составить списки входящих в нее точек. А потом перебор только по точкам от 1-й до 4-х ячеек.

                  До свидания,  в  23:54 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)