Recuento de puntos integrales que se encuentran a una distancia D del origen

Dado un entero positivo D , la tarea es encontrar el número de coordenadas enteras (x, y) que se encuentran a una distancia D del origen.

Ejemplo:

Entrada: D = 1
Salida: 4
Explicación: El total de puntos válidos son {1, 0}, {0, 1}, {-1, 0}, {0, -1}

Entrada: D = 5
Salida: 12
Explicación: El total de puntos válidos son {0, 5}, {0, -5}, {5, 0}, {-5, 0}, {3, 4}, {3, – 4}, {-3, 4}, {-3, -4}, {4, 3}, {4, -3}, {-4, 3}, {-4, -3}

Enfoque: esta pregunta se puede simplificar para contar coordenadas enteras que se encuentran en la circunferencia del círculo con centro en el origen, que tiene un radio D y se puede resolver con la ayuda del teorema de Pitágoras . Como los puntos deben estar a una distancia D del origen, todos deben satisfacer la ecuación x * x + y * y = D ² donde (x, y) son las coordenadas del punto.
Ahora, para resolver el problema anterior, siga los pasos a continuación:

• Inicializa una variable, digamos cuenta que almacena la cuenta total de los posibles pares de coordenadas .
• Iterar sobre todas las coordenadas x posibles y calcular el valor correspondiente de y como sqrt(D ² – y*y) .
• Dado que cada coordenada en la que tanto x como y son enteros positivos puede formar un total de 4 posibles pares válidos como {x, y}, {-x, y}, {-x, -y}, {x, -y} e incrementar el contar cada par posible (x, y) por 4 en la variable contar .
• Además, siempre hay una coordenada entera presente en la circunferencia del círculo donde corta el eje x y el eje y porque el radio del círculo es un número entero. Entonces agregue 4 en cuenta , para compensar estos puntos.
• Después de completar los pasos anteriores, imprima el valor de conteo como el conteo resultante de pares.

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 total valid
// integer coordinates at a distance D
// from origin
int countPoints(int D)
{
    // Stores the count of valid points
    int count = 0;
 
    // Iterate over possible x coordinates
    for (int x = 1; x * x < D * D; x++) {
 
        // Find the respective y coordinate
        // with the pythagoras theorem
        int y = (int)sqrt(double(D * D - x * x));
        if (x * x + y * y == D * D) {
            count += 4;
        }
    }
 
    // Adding 4 to compensate the coordinates
    // present on x and y axes.
    count += 4;
 
    // Return the answer
    return count;
}
 
// Driver Code
int main()
{
    int D = 5;
    cout << countPoints(D);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
// Function to find the total valid
// integer coordinates at a distance D
// from origin
static int countPoints(int D)
{
   
    // Stores the count of valid points
    int count = 0;
 
    // Iterate over possible x coordinates
    for (int x = 1; x * x < D * D; x++) {
 
        // Find the respective y coordinate
        // with the pythagoras theorem
        int y = (int)Math.sqrt((D * D - x * x));
        if (x * x + y * y == D * D) {
            count += 4;
        }
    }
 
    // Adding 4 to compensate the coordinates
    // present on x and y axes.
    count += 4;
 
    // Return the answer
    return count;
}
 
// Driver Code
public static void main (String[] args)
{
    int D = 5;
    System.out.println(countPoints(D));
}
}
 
// this code is contributed by shivanisinghss2110

# python 3 program for the above approach
from math import sqrt
 
# Function to find the total valid
# integer coordinates at a distance D
# from origin
def countPoints(D):
   
    # Stores the count of valid points
    count = 0
 
    # Iterate over possible x coordinates
    for x in range(1, int(sqrt(D * D)), 1):
 
        # Find the respective y coordinate
        # with the pythagoras theorem
        y = int(sqrt((D * D - x * x)))
        if (x * x + y * y == D * D):
            count += 4
 
    # Adding 4 to compensate the coordinates
    # present on x and y axes.
    count += 4
 
    # Return the answer
    return count
 
# Driver Code
if __name__ == '__main__':
    D = 5
    print(countPoints(D))
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
 
// Function to find the total valid
// integer coordinates at a distance D
// from origin
public class GFG{
    static int countPoints(int D){
         
        // Stores the count of valid points
        int count = 0;
         
        // Iterate over possible x coordinates
        for(int x = 1; x*x < D*D; x++){
            int y = (int)Math.Sqrt((D * D - x * x));
 
            // Find the respective y coordinate
            // with the pythagoras theorem
            if(x * x + y * y == D * D){
              count += 4;  
            }
       }
    // Adding 4 to compensate the coordinates
    // present on x and y axes.
     
    count += 4;
 
    // Return the answer
    return count;
}
     
    // Driver Code
 
    public static void Main(){
        int D = 5;
        Console.Write(countPoints(D));
    }
}
 
// This code is contributed by gfgking

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the total valid
        // integer coordinates at a distance D
        // from origin
        function countPoints(D)
        {
         
            // Stores the count of valid points
            let count = 0;
 
            // Iterate over possible x coordinates
            for (let x = 1; x * x < D * D; x++) {
 
                // Find the respective y coordinate
                // with the pythagoras theorem
                let y = Math.floor(Math.sqrt(D * D - x * x));
                if (x * x + y * y == D * D) {
                    count += 4;
                }
            }
 
            // Adding 4 to compensate the coordinates
            // present on x and y axes.
            count += 4;
 
            // Return the answer
            return count;
        }
 
        // Driver Code
        let D = 5;
        document.write(countPoints(D));
 
     // This code is contributed by Potta Lokesh
    </script>

12

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