Contar pares de coordenadas conectadas por una línea con pendiente en el rango [-K, K]

Dado un entero K y dos arrays X[] e Y[], ambas compuestas por N enteros, donde (X[i], Y[i]) es una coordenada en un plano, la tarea es encontrar el número total de pares de puntos tales que la línea que pasa por ellos tiene una pendiente en el rango [-K, K] .

Ejemplos:

Entrada: X[] = {2, 1, 0}, Y[] = {1, 2, 0}, K = 1
Salida: 2
Explicación:
El conjunto de pares que satisfacen la condición dada son [(0, 0), (2, 1)] y [(1, 2), (2, 1)].

Entrada: X[] = {2, 4}, Y[][] = {5, 6}, K = 1
Salida: 1

Enfoque: La idea es atravesar todos los pares de puntos y verificar si su pendiente se encuentra en el rango [-K, K] o no. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans a 0 para almacenar el conteo resultante de pares.
• Ahora, genere todos los pares de coordenadas posibles y si la pendiente de los 2 puntos (X[i], Y[i]) y (X[j], Y[j]) se encuentra en el rango [-K, K] , luego incremente ans en 1 .
• Después de completar los pasos anteriores, imprima el valor de y como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of pairs
// of points such that the line passing
// through them has a slope in the range[-k, k]
void findPairs(vector<int> x, vector<int> y,
               int K)
{
    int n = x.size();
 
    // Store the result
    int ans = 0;
 
    // Traverse through all the
    // combination of points
    for (int i = 0; i < n; ++i) {
 
        for (int j = i + 1; j < n; ++j) {
 
            // If pair satisfies
            // the given condition
            if (K * abs(x[i] - x[j])
                >= abs(y[i] - y[j])) {
 
                // Increment ans by 1
                ++ans;
            }
        }
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    vector<int> X = { 2, 1, 0 },
                Y = { 1, 2, 0 };
    int K = 1;
 
    // Function Call
    findPairs(X, Y, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to find the number of pairs
// of points such that the line passing
// through them has a slope in the range[-k, k]
static void findPairs(int[] x, int[] y,
               int K)
{
    int n = x.length;
 
    // Store the result
    int ans = 0;
 
    // Traverse through all the
    // combination of points
    for (int i = 0; i < n; ++i) {
 
        for (int j = i + 1; j < n; ++j) {
 
            // If pair satisfies
            // the given condition
            if (K * Math.abs(x[i] - x[j])
                >= Math.abs(y[i] - y[j])) {
 
                // Increment ans by 1
                ++ans;
            }
        }
    }
 
    // Print the result
    System.out.print(ans);
}
 
 
// Driven Code
public static void main(String[] args)
{
    int[] X = { 2, 1, 0 };
    int[] Y = { 1, 2, 0 };
    int K = 1;
 
    // Function Call
    findPairs(X, Y, K);
}
}
 
// This code is contributed by sanjoy_62.

# Python3 program for the above approach
 
# Function to find the number of pairs
# of points such that the line passing
# through them has a slope in the range[-k, k]
def findPairs(x, y, K):
    n = len(x)
 
    # Store the result
    ans = 0
 
    # Traverse through all the
    # combination of points
    for i in range(n):
        for j in range(i + 1, n):
           
            # If pair satisfies
            # the given condition
            if (K * abs(x[i] - x[j]) >= abs(y[i] - y[j])):
               
                # Increment ans by 1
                ans += 1
 
    # Print the result
    print (ans)
 
# Driver Code
if __name__ == '__main__':
    X = [2, 1, 0]
    Y = [1, 2, 0]
    K = 1
 
    # Function Call
    findPairs(X, Y, K)
 
 # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the number of pairs
// of points such that the line passing
// through them has a slope in the range[-k, k]
static void findPairs(int[] x, int[] y,
                      int K)
{
    int n = x.Length;
 
    // Store the result
    int ans = 0;
 
    // Traverse through all the
    // combination of points
    for(int i = 0; i < n; ++i)
    {
        for(int j = i + 1; j < n; ++j)
        {
             
            // If pair satisfies
            // the given condition
            if (K * Math.Abs(x[i] - x[j]) >=
                    Math.Abs(y[i] - y[j]))
            {
                 
                // Increment ans by 1
                ++ans;
            }
        }
    }
 
    // Print the result
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main(String []args)
{
    int[] X = { 2, 1, 0 };
    int[] Y = { 1, 2, 0 };
    int K = 1;
 
    // Function Call
    findPairs(X, Y, K);
}
}
 
// This code is contributed by souravghosh0416

<script>
    // Javascript program for the above approach
     
    // Function to find the number of pairs
    // of points such that the line passing
    // through them has a slope in the range[-k, k]
    function findPairs(x, y, K)
    {
        let n = x.length;
 
        // Store the result
        let ans = 0;
 
        // Traverse through all the
        // combination of points
        for (let i = 0; i < n; ++i) {
 
            for (let j = i + 1; j < n; ++j) {
 
                // If pair satisfies
                // the given condition
                if (K * Math.abs(x[i] - x[j])
                    >= Math.abs(y[i] - y[j])) {
 
                    // Increment ans by 1
                    ++ans;
                }
            }
        }
 
        // Print the result
        document.write(ans);
    }
 
  // Driver code
    let X = [ 2, 1, 0 ], Y = [ 1, 2, 0 ];
    let K = 1;
  
    // Function Call
    findPairs(X, Y, K);
     
    // This code is contributed by divyesh072019.
</script>

2

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