Cuente pares de puntos que tengan una distancia entre ellos igual a los valores integrales en un espacio de K-dimensional

Posted on by Rudeus Greyrat

Dada una array points[] que representa N puntos en un espacio de K dimensiones, la tarea es encontrar el recuento de pares de puntos en el espacio de modo que la distancia entre los puntos de cada par sea un valor entero.

Ejemplos:

Entrada: puntos[] = { {1, 2}, {5, 5}, {2, 8} }, K = 2
Salida: 1
Explicación: 
Distancia entre puntos del par(puntos[0], puntos[1] ) = 5 
Distancia entre puntos del par(puntos[1], puntos[2]) = sqrt(58) 
Distancia entre puntos del par(puntos[0], puntos[2]) = 3 * sqrt(5) 
Por lo tanto , la salida requerida es 1.

Entrada: puntos[] = { {-3, 7, 8, 2}, {-12, 1, 10, 2}, {-2, 8, 9, 3} }, K = 4
Salida: 2.

 

Enfoque: La idea es generar todos los pares posibles de la array dada y encontrar la distancia entre los puntos de cada par y verificar si es un valor entero o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo total obtenido. Siga los pasos a continuación para resolver el problema:

  • La distancia entre los puntos del par ({ a 1 , a 2 , …, a K }, { b 1 , b 2 , …, b K }) se puede calcular usando la siguiente fórmula: 
     

Distancia(a, b) = sqrt(((a 1 – b 1 ) 2 + (a 2 – b 2 ) 2 + …. + (a K – b K ) 2 ))
 

  • Recorre la array y genera todos los pares posibles de la array dada.
  • Para cada par de puntos, verifica si la distancia entre los puntos del par es un número entero o no. Si se encuentra que es cierto, entonces incremente el conteo.
  • Finalmente, imprima el conteo obtenido.

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 pairs whose distance between
// the points of is an integer value.
void cntPairs(vector<vector<int> > points, int n, int K)
{
 
    // Stores count of pairs whose distance
    // between points is an integer
    int ans = 0;
 
    // Traverse the array, points[]
    for (int i = 0; i < n; i++) {
 
        for (int j = i + 1; j < n; j++) {
 
            // Stores distance between
            // points(i, j)
            int dist = 0;
 
            // Traverse all the points of
            // current pair
            for (int k = 0; k < K; k++) {
 
                // Update temp
                int temp = (points[i][k]
                            - points[j][k]);
 
                // Update dist
                dist += temp * temp;
            }
 
            // If dist is a perfect square
            if (sqrt(dist) * sqrt(dist) == dist) {
 
                // Update ans
                ans += 1;
            }
        }
    }
 
    cout << ans << endl;
}
 
// Driver Code
int main()
{
 
    // Given value of K
    int K = 2;
 
    // Given points
    vector<vector<int> > points
        = { { 1, 2 }, { 5, 5 }, { -2, 8 } };
 
    // Given value of N
    int n = points.size();
 
    // Function Call
    cntPairs(points, n, K);
 
    return 0;
}

Java

// Java program for the above approach
class GFG
{
 
  // Function to  find pairs whose distance between
  // the points of is an integer value.
  static void cntPairs(int [][]points, int n, int K)
  {
 
    // Stores count of pairs whose distance
    // between points is an integer
    int ans = 0;
 
    // Traverse the array, points[]
    for (int i = 0; i < n; i++)
    {
      for (int j = i + 1; j < n; j++)
      {
 
        // Stores distance between
        // points(i, j)
        int dist = 0;
 
        // Traverse all the points of
        // current pair
        for (int k = 0; k < K; k++)
        {
 
          // Update temp
          int temp = (points[i][k]
                      - points[j][k]);
 
          // Update dist
          dist += temp * temp;
        }
 
        // If dist is a perfect square
        if (Math.sqrt(dist) * Math.sqrt(dist) == dist)
        {
 
          // Update ans
          ans += 1;
        }
      }
    }
    System.out.print(ans +"\n");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given value of K
    int K = 2;
 
    // Given points
    int [][]points
      = { { 1, 2 }, { 5, 5 }, { -2, 8 } };
 
    // Given value of N
    int n = points.length;
 
    // Function Call
    cntPairs(points, n, K);
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# Function to  find pairs whose distance between
# the points of is an integer value.
def cntPairs(points, n, K):
   
    # Stores count of pairs whose distance
    # between points is an integer
    ans = 0
 
    # Traverse the array, points[]
    for i in range(0, n):
 
        for j in range(i + 1, n):
 
            # Stores distance between
            # points(i, j)
            dist = 0
 
            # Traverse all the points of
            # current pair
            for k in range(K):
 
                # Update temp
                temp = (points[i][k] - points[j][k])
 
                # Update dist
                dist += temp * temp
 
            # If dist is a perfect square
            if (((dist)**(1/2)) * ((dist)**(1/2)) == dist):
 
                # Update ans
                ans += 1
    print(ans)
 
# Driver Code
# Given value of K
K = 2
 
# Given points
points = [ [ 1, 2 ], [ 5, 5 ], [ -2, 8 ]]
 
# Given value of N
n = len(points)
 
# Function Call
cntPairs(points, n, K)
 
# This code is contributed by rohitsingh07052.

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Function to  find pairs whose distance between
  // the points of is an integer value.
  static void cntPairs(int[, ] points, int n, int K)
  {
 
    // Stores count of pairs whose distance
    // between points is an integer
    int ans = 0;
 
    // Traverse the array, points[]
    for (int i = 0; i < n; i++) {
 
      for (int j = i + 1; j < n; j++) {
 
        // Stores distance between
        // points(i, j)
        int dist = 0;
 
        // Traverse all the points of
        // current pair
        for (int k = 0; k < K; k++) {
 
          // Update temp
          int temp
            = (points[i, k] - points[j, k]);
 
          // Update dist
          dist += temp * temp;
        }
 
        // If dist is a perfect square
        if (Math.Sqrt(dist) * Math.Sqrt(dist)
            == dist) {
 
          // Update ans
          ans += 1;
        }
      }
    }
 
    Console.WriteLine(ans);
  }
 
  // Driver Code
  public static void Main()
  {
 
    // Given value of K
    int K = 2;
 
    // Given points
    int[, ] points = { { 1, 2 }, { 5, 5 }, { -2, 8 } };
 
    // Given value of N
    int n = points.GetLength(0);
 
    // Function Call
    cntPairs(points, n, K);
  }
}
 
// This code is contributed by chitranayal.

Javascript

<script>
 
// javascript program for the above approach   
// Function to find pairs whose distance between
    // the points of is an integer value.
    function cntPairs(points , n , K) {
 
        // Stores count of pairs whose distance
        // between points is an integer
        var ans = 0;
 
        // Traverse the array, points
        for (i = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) {
 
                // Stores distance between
                // points(i, j)
                var dist = 0;
 
                // Traverse all the points of
                // current pair
                for (k = 0; k < K; k++) {
 
                    // Update temp
                    var temp = (points[i][k] -
                    points[j][k]);
 
                    // Update dist
                    dist += temp * temp;
                }
 
                // If dist is a perfect square
                if (Math.sqrt(dist) *
                Math.sqrt(dist) == dist)
                {
 
                    // Update ans
                    ans += 1;
                }
            }
        }
        document.write(ans + "\n");
    }
 
    // Driver Code
     
 
        // Given value of K
        var K = 2;
 
        // Given points
        var points = [ [ 1, 2 ], [ 5, 5 ],
        [ -2, 8 ] ];
 
        // Given value of N
        var n = points.length;
 
        // Function Call
        cntPairs(points, n, K);
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

1

 

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

Publicación traducida automáticamente

Artículo escrito por huzaifa0602 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 *