|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 10 Aug 2002 00:00:40
To : Evgenij M. Baldin
Subject : Re: Сортировка комплексных чисел?
--------------------------------------------------------------------------------
Однажды 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> Hадо найти такое 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
