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) = 32Entrada: 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>
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