Suma de cuadrados de distancias entre todos los pares desde puntos dados

Dada una array arr[] que consta de coordenadas de N puntos en un plano XY , la tarea es encontrar la suma de las distancias al cuadrado entre todos los pares de puntos, es decir, (X i – X j ) 2 + (Y i – Y j ) 2 para cada par distinto (i, j) .

Ejemplos:

Entrada: arr[][] = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}}
Salida: 32
Explicación: 
Distancia del 1er punto (1, 1) del 2 ° , 3 ° y 4 ° punto son 8, 4 y 4 respectivamente.
La distancia del 2 ° punto desde el 3 ° y 4 ° punto es 4 y 4 respectivamente.
La distancia del 3er punto al 4to punto es 8.
Por lo tanto, la distancia total = (8 + 4 + 4) + (4 + 4) + (8) = 32

Entrada: arr[][] = {{1, 1}, {1, 1}, {0, 0}}
Salida: 4
Explicación:
La distancia del primer punto desde el segundo y el tercer punto son 0 y 2 respectivamente .
La distancia del 2 ° punto al 3 ° punto es 2.
Por lo tanto, la distancia total = (0 + 2) + (2) = 4

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares distintos posibles de la array dada arr[][] y calcular la suma de los cuadrados de las distancias entre todos los pares de puntos (X i , Y j ) y (X j , Y j ), es decir (X i – X j ) 2 + (Y i – Y j ) 2 , para cada par distinto (i, j)

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es reagrupar la suma y dividir la suma de los cuadrados de las distancias en dos sumas. Siga los pasos a continuación para resolver el problema:

  • Inicialice variables, digamos xq , yq , xs e ys .
  • Inicialice una variable, digamos res , con cero , para almacenar la suma resultante.
  • Recorra la array dada y para cada punto {x, y} , realice los siguientes pasos:
    • Sume el valor de (i*x 2 + i*y 2 ) en la variable res , que corresponde a la suma de la distancia al cuadrado.
    • Agregue el valor (xq – 2 * xs * a) y (yq – 2 * ys * b) a res para anular el efecto de 2 * X * Y en la expansión de (a – b) 2 .
    • Sume los valores a 2 y b 2 a las variables xq y yq respectivamente.
    • Sume los valores a y b a las variables xs e ys respectivamente.
    • Sume los valores xs y yq a las variables a 2 y b 2 respectivamente.
  • Después de completar los pasos anteriores, imprima el valor de res como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of squares
// of distance between all distinct pairs
void findSquareSum(
    int Coordinates[][2], int N)
{
    long long xq = 0, yq = 0;
    long long xs = 0, ys = 0;
 
    // Stores final answer
    long long res = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        int a, b;
 
        a = Coordinates[i][0];
        b = Coordinates[i][1];
 
        res += xq;
        res -= 2 * xs * a;
 
        // Adding the effect of this
        // point for all the previous
        // x - points
        res += i * (long long)(a * a);
 
        // Temporarily add the
        // square of x-coordinate
        xq += a * a;
        xs += a;
        res += yq;
        res -= 2 * ys * b;
        res += i * (long long)b * b;
 
        // Add the effect of this point
        // for all the previous y - points
        yq += b * b;
        ys += b;
    }
 
    // Print the desired answer
    cout << res;
}
 
// Driver Code
int main()
{
    int arr[][2] = { { 1, 1 },
                     { -1, -1 },
                     { 1, -1 },
                     { -1, 1 } };
    int N = sizeof(arr) / sizeof(arr[0]);
    findSquareSum(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
  // Function to find the sum of squares
  // of distance between all distinct pairs
  static void findSquareSum(
    int Coordinates[][], int N)
  {
    long xq = 0, yq = 0;
    long xs = 0, ys = 0;
 
    // Stores final answer
    long res = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
      int a, b;
 
      a = Coordinates[i][0];
      b = Coordinates[i][1];
 
      res += xq;
      res -= 2 * xs * a;
 
      // Adding the effect of this
      // point for all the previous
      // x - points
      res += i * (long)(a * a);
 
      // Temporarily add the
      // square of x-coordinate
      xq += a * a;
      xs += a;
      res += yq;
      res -= 2 * ys * b;
      res += i * (long)b * b;
 
      // Add the effect of this point
      // for all the previous y - points
      yq += b * b;
      ys += b;
    }
 
    // Print the desired answer
    System.out.println(res);
  }
 
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[][] = { { 1, 1 },
                   { -1, -1 },
                   { 1, -1 },
                   { -1, 1 } };
    int N = arr.length;
    findSquareSum(arr, N);
  }
}
 
// This code is contributed by code_hunt.

Python3

# Python3 program for the above approach
 
# Function to find the sum of squares
# of distance between all distinct pairs
def findSquareSum(Coordinates, N):
    xq , yq = 0, 0
    xs , ys = 0, 0
 
    # Stores final answer
    res = 0
 
    # Traverse the array
    for i in range(N):
 
        a = Coordinates[i][0]
        b = Coordinates[i][1]
 
        res += xq
        res -= 2 * xs * a
 
        # Adding the effect of this
        # point for all the previous
        # x - points
        res += i * (a * a)
 
        # Temporarily add the
        # square of x-coordinate
        xq += a * a
        xs += a
        res += yq
        res -= 2 * ys * b
        res += i * b * b
 
        # Add the effect of this point
        # for all the previous y - points
        yq += b * b
        ys += b
 
    # Print the desired answer
    print (res)
 
# Driver Code
if __name__ == '__main__':
    arr = [ [ 1, 1 ],
         [ -1, -1 ],
         [ 1, -1 ],
         [ -1, 1 ] ]
 
    N = len(arr)
 
    findSquareSum(arr, N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the sum of squares
// of distance between all distinct pairs
static void findSquareSum(int[,] Coordinates, int N)
{
    long xq = 0, yq = 0;
    long xs = 0, ys = 0;
     
    // Stores final answer
    long res = 0;
     
    // Traverse the array
    for(int i = 0; i < N ; i++)
    {
        int a, b;
         
        a = Coordinates[i, 0];
        b = Coordinates[i, 1];
         
        res += xq;
        res -= 2 * xs * a;
         
        // Adding the effect of this
        // point for all the previous
         
        // x - points
        res += i * (long)(a * a);
         
        // Temporarily add the
        // square of x-coordinate
        xq += a * a;
        xs += a;
        res += yq;
        res -= 2 * ys * b;
        res += i * (long)b * b;
         
        // Add the effect of this point
        // for all the previous y - points
        yq += b * b;
        ys += b;
    }
     
    // Print the desired answer
    Console.Write(res);
}
 
// Driver code
static void Main()
{
    int[,] arr = { { 1, 1 },
                   { -1, -1 },
                   { 1, -1 },
                   { -1, 1 } };
    int N = arr.GetLength(0);
     
    findSquareSum(arr, N);
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// Javascript program for the above approach
 
  // Function to find the sum of squares
  // of distance between all distinct pairs
  function findSquareSum(
    Coordinates, N)
  {
    let xq = 0, yq = 0;
    let xs = 0, ys = 0;
 
    // Stores final answer
    let res = 0;
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
      let a, b;
 
      a = Coordinates[i][0];
      b = Coordinates[i][1];
 
      res += xq;
      res -= 2 * xs * a;
 
      // Adding the effect of this
      // point for all the previous
      // x - points
      res += i * (a * a);
 
      // Temporarily add the
      // square of x-coordinate
      xq += a * a;
      xs += a;
      res += yq;
      res -= 2 * ys * b;
      res += i * b * b;
 
      // Add the effect of this point
      // for all the previous y - points
      yq += b * b;
      ys += b;
    }
 
    // Print the desired answer
    document.write(res);
  }
 
// Driver code
     
    let arr = [[ 1, 1 ],
               [ -1, -1 ],
               [ 1, -1 ],
               [ -1, 1 ]];
    let N = arr.length;
    findSquareSum(arr, N);
     
</script>
Producción: 

32

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *