Suma de las distancias de Manhattan entre todos los pares de puntos

Dadas n coordenadas enteras. La tarea es encontrar la suma de la distancia de Manhattan entre todos los pares de coordenadas.
Manhattan La distancia entre dos puntos (x ₁ , y ₁ ) y (x ₂ , y ₂ ) es:
|x ₁ – x ₂ | + |y ₁ – y ₂ |
Ejemplos:

Input : n = 4
        point1 = { -1, 5 }
        point2 = { 1, 6 }
        point3 = { 3, 5 }
        point4 = { 2, 3 }
Output : 22
Distance of { 1, 6 }, { 3, 5 }, { 2, 3 } from 
{ -1, 5 } are 3, 4, 5 respectively.
Therefore, sum = 3 + 4 + 5 = 12

Distance of { 3, 5 }, { 2, 3 } from { 1, 6 } 
are 3, 4 respectively.
Therefore, sum = 12 + 3 + 4 = 19

Distance of { 2, 3 } from { 3, 5 } is 3.
Therefore, sum = 19 + 3 = 22.

Método 1: (Fuerza bruta)

Complejidad de tiempo: O(n ² )
La idea es ejecutar dos bucles anidados, es decir, para cada punto, encontrar la distancia de Manhattan para todos los demás puntos.

for (i = 1; i < n; i++)

  for (j = i + 1; j < n; j++)

    sum += ((x_i - x_j) + (y_i - y_j))

A continuación se muestra la implementación de este enfoque:

C++

// CPP Program to find sum of Manhattan distance
// between all the pairs of given points
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of distance between all
// the pair of points.
int distancesum(int x[], int y[], int n)
{
    int sum = 0;
 
    // for each point, finding distance to
    // rest of the point
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            sum += (abs(x[i] - x[j]) + abs(y[i] - y[j]));
    return sum;
}
 
// Driven Program
int main()
{
    int x[] = { -1, 1, 3, 2 };
    int y[] = { 5, 6, 5, 3 };
    int n = sizeof(x) / sizeof(x[0]);
    cout << distancesum(x, y, n) << endl;
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C Program to find sum of Manhattan distance
// between all the pairs of given points
#include <stdio.h>
#include <stdlib.h>
 
// Return the sum of distance between all
// the pair of points.
int distancesum(int x[], int y[], int n)
{
    int sum = 0;
 
    // for each point, finding distance to
    // rest of the point
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            sum += (abs(x[i] - x[j]) + abs(y[i] - y[j]));
    return sum;
}
 
// Driven Program
int main()
{
    int x[] = { -1, 1, 3, 2 };
    int y[] = { 5, 6, 5, 3 };
    int n = sizeof(x) / sizeof(x[0]);
    printf("%d\n", distancesum(x, y, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java Program to find sum of Manhattan distance
// between all the pairs of given points
 
import java.io.*;
 
class GFG {
 
    // Return the sum of distance between all
    // the pair of points.
    static int distancesum(int x[], int y[], int n)
    {
        int sum = 0;
 
        // for each point, finding distance to
        // rest of the point
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                sum += (Math.abs(x[i] - x[j])
                        + Math.abs(y[i] - y[j]));
        return sum;
    }
 
    // Driven Program
    public static void main(String[] args)
    {
        int x[] = { -1, 1, 3, 2 };
        int y[] = { 5, 6, 5, 3 };
        int n = x.length;
 
        System.out.println(distancesum(x, y, n));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 code to find sum of
# Manhattan distance between all
# the pairs of given points
 
# Return the sum of distance
# between all the pair of points.
def distancesum (x, y, n):
    sum = 0
     
    # for each point, finding distance
    # to rest of the point
    for i in range(n):
        for j in range(i+1,n):
            sum += (abs(x[i] - x[j]) +
                        abs(y[i] - y[j]))
     
    return sum
 
# Driven Code
x = [ -1, 1, 3, 2 ]
y = [ 5, 6, 5, 3 ]
n = len(x)
print(distancesum(x, y, n) )
 
# This code is contributed by "Sharad_Bhardwaj".

C#

// C# Program to find sum of Manhattan distance
// between all the pairs of given points
using System;
 
class GFG {
     
    // Return the sum of distance between all
    // the pair of points.
    static int distancesum(int []x, int []y, int n)
    {
        int sum = 0;
 
        // for each point, finding distance to
        // rest of the point
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                sum += (Math.Abs(x[i] - x[j]) +
                            Math.Abs(y[i] - y[j]));
        return sum;
    }
 
    // Driven Program
    public static void Main()
    {
        int []x = { -1, 1, 3, 2 };
        int []y = { 5, 6, 5, 3 };
        int n = x.Length;
         
        Console.WriteLine(distancesum(x, y, n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find sum
// of Manhattan distance
// between all the pairs
// of given points
 
// Return the sum of distance
// between all the pair of points.
function distancesum( $x, $y, $n)
{
    $sum = 0;
 
    // for each point, finding
    // distance to rest of
    // the point
    for($i = 0; $i < $n; $i++)
        for ($j = $i + 1; $j < $n; $j++)
            $sum += (abs($x[$i] - $x[$j]) +
                     abs($y[$i] - $y[$j]));
    return $sum;
}
 
    // Driver Code
    $x = array(-1, 1, 3, 2);
    $y = array(5, 6, 5, 3);
    $n = count($x);
    echo distancesum($x, $y, $n);
     
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript Program to find sum of Manhattan distance
// between all the pairs of given points
 
    // Return the sum of distance between all
    // the pair of points.
    function distancesum(x, y, n)
    {
        let sum = 0;
  
        // for each point, finding distance to
        // rest of the point
        for (let i = 0; i < n; i++)
            for (let j = i + 1; j < n; j++)
                sum += (Math.abs(x[i] - x[j]) +
                            Math.abs(y[i] - y[j]));
        return sum;
    }
 
// Driver code
        let x = [ -1, 1, 3, 2 ];
        let y = [ 5, 6, 5, 3 ];
        let n = x.length;
          
        document.write(distancesum(x, y, n));
          
         // This code is contributed by sanjoy_62.
</script>

Producción:

Tiempo Complejidad: O(n ² )
Espacio Auxiliar: O(1)

Método 2: (Enfoque eficiente)

La idea es utilizar el enfoque codicioso. Primero observe, la fórmula de Manhattan se puede descomponer en dos sumas independientes, una para la diferencia entre las coordenadas x y la segunda entre las coordenadas y . Si sabemos cómo calcular uno de ellos, podemos usar el mismo método para calcular el otro. Así que ahora nos limitaremos a calcular la suma de las coordenadas x de la distancia.
Supongamos que hemos calculado la suma de distancias entre dos puntos cualesquiera hasta un punto x _i-1 para todos los valores de x menores que x _i-1 , dejemos que esta suma sea res y ahora tenemos que calcular la distancia entre cualquier dos puntos con x _i incluido, donde x _i es el siguiente punto mayor, Para calcular la distancia de cada punto al siguiente punto mayor x _i , podemos sumar la suma de diferencias existente res con la distancia de x _i a todos los puntos x _k que son menores que x _i. Por lo tanto, la suma entre dos puntos cualesquiera ahora será igual a res + ∑ ( x _i – x _k ) , donde x _i es el punto actual desde el cual se miden las diferencias, y x _k son todos los puntos menores que x _i .
Debido a que para cada cálculo x _i sigue siendo el mismo, podemos simplificar la suma como:

res = res + (x _i – x ₀ ) + (x _i – x ₁ ) + (x _i – x ₂ ) + (x _i – x ₃ )………(x _i – x _i-1 )

res = res + (x _i )*i – (x ₀ +x ₁ + x ₂ + …… x _i-1 ) , porque en una array ordenada, hay i elementos más pequeños que el índice actual i .

res = res + (x _i )*i – S _i-1 , donde S _i-1 es la suma de todos los puntos anteriores hasta el índice i – 1

4. Para el nuevo índice i, necesitamos sumar la diferencia del índice actual x _i de todos los índices anteriores x _k < x _i

5. Si clasificamos todos los puntos en orden no decreciente, podemos calcular fácilmente la suma deseada de distancias a lo largo de un eje entre cada par de coordenadas en tiempo O(N), procesando los puntos de izquierda a derecha y usando el método anterior.
Además, no tenemos que preocuparnos si dos puntos tienen coordenadas iguales, después de ordenar los puntos en orden no decreciente, decimos que un punto x _i-1 es x _i más pequeño si y solo si aparece antes en la array ordenada.
A continuación se muestra la implementación de este enfoque:

C++

// CPP Program to find sum of Manhattan
// distances between all the pairs of
// given points
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of distance of one axis.
int distancesum(int arr[], int n)
{
    // sorting the array.
    sort(arr, arr + n);
 
    // for each point, finding the distance.
    int res = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        res += (arr[i] * i - sum);
        sum += arr[i];
    }
 
    return res;
}
 
int totaldistancesum(int x[], int y[], int n)
{
    return distancesum(x, n) + distancesum(y, n);
}
 
// Driven Program
int main()
{
    int x[] = { -1, 1, 3, 2 };
    int y[] = { 5, 6, 5, 3 };
    int n = sizeof(x) / sizeof(x[0]);
    cout << totaldistancesum(x, y, n) << endl;
    return 0;
}

Java

// Java Program to find sum of Manhattan
// distances between all the pairs of
// given points
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    // Return the sum of distance of one axis.
    static int distancesum(int arr[], int n)
    {
         
        // sorting the array.
        Arrays.sort(arr);
 
        // for each point, finding the distance.
        int res = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            res += (arr[i] * i - sum);
            sum += arr[i];
        }
 
        return res;
    }
 
    static int totaldistancesum(int x[],
                            int y[], int n)
    {
        return distancesum(x, n) +
                        distancesum(y, n);
    }
 
    // Driven Program
    public static void main(String[] args)
    {
 
        int x[] = { -1, 1, 3, 2 };
        int y[] = { 5, 6, 5, 3 };
        int n = x.length;
        System.out.println(totaldistancesum(x,
                                        y, n));
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 code to find sum of Manhattan
# distances between all the pairs of
# given points
 
# Return the sum of distance of one axis.
def distancesum (arr, n):
     
    # sorting the array.
    arr.sort()
     
    # for each point, finding
    # the distance.
    res = 0
    sum = 0
    for i in range(n):
        res += (arr[i] * i - sum)
        sum += arr[i]
     
    return res
     
def totaldistancesum( x , y , n ):
    return distancesum(x, n) + distancesum(y, n)
     
# Driven Code
x = [ -1, 1, 3, 2 ]
y = [ 5, 6, 5, 3 ]
n = len(x)
print(totaldistancesum(x, y, n) )
 
# This code is contributed by "Sharad_Bhardwaj".

C#

// C# Program to find sum of Manhattan
// distances between all the pairs of
// given points
 
using System;
 
class GFG {
     
    // Return the sum of distance of one axis.
    static int distancesum(int []arr, int n)
    {
         
        // sorting the array.
        Array.Sort(arr);
 
        // for each point, finding the distance.
        int res = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            res += (arr[i] * i - sum);
            sum += arr[i];
        }
 
        return res;
    }
 
    static int totaldistancesum(int []x,
                            int []y, int n)
    {
        return distancesum(x, n) +
                        distancesum(y, n);
    }
 
    // Driven Program
    public static void Main()
    {
 
        int []x = { -1, 1, 3, 2 };
        int []y = { 5, 6, 5, 3 };
        int n = x.Length;
        Console.WriteLine(totaldistancesum(x,
                                        y, n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find sum of
// Manhattan distances between
// all the pairs of given points
 
// Return the sum of
// distance of one axis.
function distancesum($arr, $n)
{
    // sorting the array.
    sort($arr);
 
    // for each point,
    // finding the distance.
    $res = 0; $sum = 0;
    for ($i = 0; $i < $n; $i++)
    {
        $res += ($arr[$i] * $i - $sum);
        $sum += $arr[$i];
    }
 
    return $res;
}
 
function totaldistancesum($x, $y, $n)
{
    return distancesum($x, $n) +
           distancesum($y, $n);
}
 
// Driver Code
$x = array(-1, 1, 3, 2);
$y = array(5, 6, 5, 3);
$n = sizeof($x);
echo totaldistancesum($x, $y, $n), "\n";
 
// This code is contributed by m_kit
?>

Javascript

<script>
 
// JavaScript Program to find sum of Manhattan
// distances between all the pairs of
// given points
 
    // Return the sum of distance of one axis.
    function distancesum(arr, n)
    {
          
        // sorting the array.
        arr.sort();
  
        // for each point, finding the distance.
        let res = 0, sum = 0;
        for (let i = 0; i < n; i++) {
            res += (arr[i] * i - sum);
            sum += arr[i];
        }
  
        return res;
    }
  
    function totaldistancesum(x,
                            y, n)
    {
        return distancesum(x, n) +
                        distancesum(y, n);
    }
      
 
// Driver code
         
        let x = [ -1, 1, 3, 2 ];
        let y = [ 5, 6, 5, 3 ];
        let n = x.length;
        document.write(totaldistancesum(x,
                                        y, n));
                   
</script>

Producción :

Complejidad de tiempo: O(n log n)
Espacio auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por anuj0503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

C

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta