Подсчитать количество пар точек с заданным манхэттенским расстоянием

Question

У меня есть P точек с целочисленными координатами (обозначается (xi, yi) ).

0 <= xi <= n;0 <= yi <= m (i = 1,2 ... P) </p>

2 <= n, m <= 100 </p>

Мне интересно узнать, сколько пар точекточно d расстояние друг от друга.Понятно, что 1 <= d <= m + n-2 и P <= m * n.Я хочу рассчитать количество пар для каждого <strong>d .Какой самый быстрый путь к этому?(Я могу найти это, зацикливаясь на d и проверяя каждую пару для каждой пары. Это очень медленный процесс)

e.g.
points : (0,2);(0,3);(2,1)
for d=1 : 1 pair
for d=2 : 0 pairs
for d=3 : 1 pair
for d=4 : 1 pair
for d=5 : 0 pairs

Answer 1

Ниже приведен алгоритм со сложностью N × M для получения количества пар точек на одном расстоянии d.Чтобы получить сумму для всех расстояний, запустите этот алгоритм для каждого значения d.Общая сложность будет тогда N × M × (N + M), что должно соответствовать ограничению по времени.

(Существуют альтернативные подходы; вы можете построить сетку с промежуточными суммами 1 на каждую диагональ, а затем считать число 1 на каждой диагонали на расстоянии d от определенной точки, вычитая два числа.будет иметь аналогичную теоретическую сложность, но может быть быстрее в реальном выражении.)

---

(Мы будем использовать входные данные, заданные в виде двоичной сетки, как в первоначальном вопросе о CodeChef, а не каксписок координат, как вы предлагаете.)

Давайте посмотрим на геометрию манхэттенского расстояния:

 6 5 4 3 4 5 6
 5 4 3 2 3 4 5
 4 3 2 1 2 3 4
 3 2 1 X 1 2 3
 4 3 2 1 2 3 4
 5 4 3 2 3 4 5
 6 5 4 3 4 5 6

Вы заметите, что точки на расстоянии d находятся на диагональных линиях, образуявокруг точки ромба, и их 4 × d;например, для расстояния d = 3:

       3
     3 . 3
   3 . . . 3
 3 . . X . . 3
   3 . . . 3
     3 . 3
       3

Мы не хотим считать каждую пару дважды, поэтому мы рассмотрим только две из четырех сторон алмаза:

       A
     . . A
   . . . . A
 . . . X . . B
   . . . . B
     . . B
       .

Если центральная точка X имеет значение 1, то сумма значений точек A и B может быть добавлена ​​к сумме пар, находящихся на расстоянии d.

Мы можем перебрать сетку, чтобы найти сумму в двух диагональных движениях;во-первых, давайте проверим точки А на верхней правой стороне ромба вокруг каждой точки.Мы смотрим на диагонали, которые находятся на расстоянии d друг от друга, например, для сетки 7 × 6 с расстоянием 3:

 . . . . . . .     . . . . . . .     A . . . . . .     . A . . . . .
 . . . . . . .     A . . . . . .     . A . . . . .     . . A . . . .
 A . . . . . .     . A . . . . .     . . A . . . .     X . . A . . .
 . A . . . . .     . . A . . . .     X . . A . . .     . X . . A . .
 . . A . . . .     X . . A . . .     . X . . A . .     . . X . . A .
 X . . A . . .     . X . . A . .     . . X . . A .     . . . X . . A     etc...

Для каждого из них мы итерируем по X-диагонали, и если значениеточки X равен 1, мы добавляем сумму значений d точек A, которые находятся над ней, к общей сумме, например:

 A . . . . . .     . . . . . . .     . . . . . . .
 . A . . . . .     . A . . . . .     . . . . . . .
 . . A . . . .     . . A . . . .     . . A . . . .
 X . . . . . .     . . . A . . .     . . . A . . .
 . . . . . . .     . X . . . . .     . . . . A . .
 . . . . . . .     . . . . . . .     . . X . . . .

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

Затем мы делаем то же самое для диагоналей в другом направлении:

 X . . B . . .     . X . . B . .     . . X . . B .     . . . X . . B
 . . B . . . .     X . . B . . .     . X . . B . .     . . X . . B .
 . B . . . . .     . . B . . . .     X . . B . . .     . X . . B . .
 B . . . . . .     . B . . . . .     . . B . . . .     X . . B . . .
 . . . . . . .     B . . . . . .     . B . . . . .     . . B . . . .
 . . . . . . .     . . . . . . .     B . . . . . .     . B . . . . .     etc...

Мы выполняем итерацию по каждой диагонали (в обоих направлениях) один раз, поэтому в конечном итоге мы итерировали по каждой точкев два раза, а сложность алгоритма линейна по M × N.

Answer 2

Почему бы вам просто не перебрать все пары точек и не вычислить расстояние, а получить карту с ключом, в котором расстояние и значение являются частотой?

for point P1 in P
   for point P2 in P, P2 > P1
      d <- distance(P1,P2) 
      if (mapDistance.get(d) exists)
         increment mapDistance.get(d)
      else 
         mapDistance.put(d,1)

Общая сложность равна O (P * P)