Puntos de círculo y celosía

Dado un círculo de radio r en 2-D con origen o (0, 0) como centro. La tarea es encontrar los puntos de red totales en la circunferencia. Los puntos de celosía son puntos con coordenadas como números enteros en el espacio 2-D.
Ejemplo: 
 

Input  : r = 5.
Output : 12
Below are lattice points on a circle with
radius 5 and origin as (0, 0).
(0,5), (0,-5), (5,0), (-5,0),
(3,4), (-3,4), (-3,-4), (3,-4),
(4,3), (-4,3), (-4,-3), (4,-3).
are 12 lattice point.

Para encontrar puntos de red, básicamente necesitamos encontrar valores de (x, y) que satisfagan la ecuación x ² + y ² = r ² . 
Para cualquier valor de (x, y) que satisfaga la ecuación anterior, en realidad tenemos un total de 4 combinaciones diferentes que satisfacen la ecuación. Por ejemplo, si r = 5 y (3, 4) es un par que satisface la ecuación, en realidad hay 4 combinaciones (3, 4) , (-3,4) , (-3,-4) , (3,- 4). Sin embargo, hay una excepción, en el caso de (0, r) o (r, 0) en realidad hay 2 puntos ya que no hay un 0 negativo.
 

// Initialize result as 4 for (r, 0), (-r. 0),
// (0, r) and (0, -r)
result = 4

Loop for x = 1 to r-1 and do following for every x.
    If r*r - x*x is a perfect square, then add 4 
    tor result.  

A continuación se muestra la implementación de la idea anterior. 
 

// C++ program to find countLattice points on a circle
#include<bits/stdc++.h>
using namespace std;
 
// Function to count Lattice points on a circle
int countLattice(int r)
{
    if (r <= 0)
        return 0;
 
    // Initialize result as 4 for (r, 0), (-r. 0),
    // (0, r) and (0, -r)
    int result = 4;
 
    // Check every value that can be potential x
    for (int x=1; x<r; x++)
    {
        // Find a potential y
        int ySquare = r*r - x*x;
        int y = sqrt(ySquare);
 
        // checking whether square root is an integer
        // or not. Count increments by 4 for four
        // different quadrant values
        if (y*y == ySquare)
            result += 4;
    }
 
    return result;
}
 
// Driver program
int main()
{
    int r = 5;
    cout << countLattice(r);
    return 0;
}

// Java program to find
// countLattice points on a circle
 
class GFG
{
 
// Function to count
// Lattice points on a circle
static int countLattice(int r)
{
    if (r <= 0)
        return 0;
  
    // Initialize result as 4 for (r, 0), (-r. 0),
    // (0, r) and (0, -r)
    int result = 4;
  
    // Check every value that can be potential x
    for (int x=1; x<r; x++)
    {
        // Find a potential y
        int ySquare = r*r - x*x;
        int y = (int)Math.sqrt(ySquare);
  
        // checking whether square root is an integer
        // or not. Count increments by 4 for four
        // different quadrant values
        if (y*y == ySquare)
            result += 4;
    }
  
    return result;
}
 
// Driver code
public static void main(String arg[])
{
    int r = 5;
    System.out.println(countLattice(r));
}
}
// This code is contributed by Anant Agarwal.

# Python3 program to find
# countLattice points on a circle
 
import math
 
# Function to count Lattice
# points on a circle
def countLattice(r):
 
    if (r <= 0):
        return 0 
 
    # Initialize result as 4 for (r, 0), (-r. 0),
    # (0, r) and (0, -r)
    result = 4
 
    # Check every value that can be potential x
    for x in range(1, r):
     
        # Find a potential y
        ySquare = r*r - x*x
        y = int(math.sqrt(ySquare))
 
        # checking whether square root is an integer
        # or not. Count increments by 4 for four
        # different quadrant values
        if (y*y == ySquare):
            result += 4
      
 
    return result
  
 
# Driver program
r = 5
print(countLattice(r))
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program to find countLattice
// points on a circle
using System;
 
class GFG {
 
    // Function to count Lattice
    // points on a circle
    static int countLattice(int r)
    {
        if (r <= 0)
            return 0;
     
        // Initialize result as 4
        // for (r, 0), (-r. 0),
        // (0, r) and (0, -r)
        int result = 4;
     
        // Check every value that
        // can be potential x
        for (int x = 1; x < r; x++)
        {
             
            // Find a potential y
            int ySquare = r*r - x*x;
            int y = (int)Math.Sqrt(ySquare);
     
            // checking whether square root
            // is an integer or not. Count
            // increments by 4 for four
            // different quadrant values
            if (y*y == ySquare)
                result += 4;
        }
     
        return result;
    }
     
    // Driver code
    public static void Main()
    {
        int r = 5;
         
        Console.Write(countLattice(r));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find countLattice
// points on a circle
 
// Function to count Lattice
// points on a circle
function countLattice($r)
{
    if ($r <= 0)
        return 0;
 
    // Initialize result as 4
    // for (r, 0), (-r. 0),
    // (0, r) and (0, -r)
    $result = 4;
 
    // Check every value that
    // can be potential x
    for ($x = 1; $x < $r; $x++)
    {
         
        // Find a potential y
        $ySquare = $r * $r - $x * $x;
        $y = ceil(sqrt($ySquare));
 
        // checking whether square
        // root is an integer
        // or not. Count increments
        // by 4 for four different
        // quadrant values
        if ($y * $y == $ySquare)
            $result += 4;
    }
 
    return $result;
}
 
    // Driver Code
    $r = 5;
    echo countLattice($r);
 
// This code is contributed by nitin mittal
?>

<script>
// javascript program to find
// countLattice points on a circle
 
    // Function to count
    // Lattice points on a circle
    function countLattice(r) {
        if (r <= 0)
            return 0;
 
        // Initialize result as 4 for (r, 0), (-r. 0),
        // (0, r) and (0, -r)
        var result = 4;
 
        // Check every value that can be potential x
        for (x = 1; x < r; x++)
        {
         
            // Find a potential y
            var ySquare = r * r - x * x;
            var y = parseInt( Math.sqrt(ySquare));
 
            // checking whether square root is an integer
            // or not. Count increments by 4 for four
            // different quadrant values
            if (y * y == ySquare)
                result += 4;
        }
 
        return result;
    }
 
    // Driver code
        var r = 5;
        document.write(countLattice(r));
 
// This code is contributed by umadevi9616
</script>

Producción: 
 

12

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Referencia:  
http://mathworld.wolfram.com/CircleLatticePoints.html
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.