Circle and Lattice Points

Given a circle of radius r in 2-D with origin or (0, 0) as center. The task is to find the total lattice points on circumference. Lattice Points are points with coordinates as integers in 2-D space.

Example:

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.

To find lattice points, we basically need to find values of (x, y) which satisfy the equation x2 + y2 = r2.
For any value of (x, y) that satisfies the above equation we actually have total 4 different combination which that satisfy the equation. For example if r = 5 and (3, 4) is a pair which satisfies the equation, there are actually 4 combinations (3, 4) , (-3,4) , (-3,-4) , (3,-4). There is an exception though, in case of (0, r) or (r, 0) there are actually 2 points as there is no negative 0.

// 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.

Below is the implementation of above idea.

CPP

 // C++ program to find countLattice points on a circle #include 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

/div>

Java

 // 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

Python3

 # Python3 program to find # countLattice podefs on a circle    import math    # Function to count Lattice # podefs 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 defeger         # 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#

 // 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.



Output:

12

tags:

Geometric Geometric