Determine el número de cuadrados de unidad de área por los que pasará una línea dada.

Dados 2 extremos (x1, y1) y (x2, y2) de una línea, la tarea es determinar el número de cuadrados de la unidad de área por los que pasará esa línea.
 

Ejemplos: 
 

Entrada: (x1 = 1, y1 = 1), (x2 = 4, y2 = 3) 
Salida: 4 
En el diagrama de arriba, la línea pasa por 4 cuadrados
Entrada: (x1 = 0, y1 = 0), (x2 = 2, y2 = 2) 
Salida: 2 
 

Enfoque : 
Vamos, 
 

Dx = (x2 - x1)
Dy = (y2 - y1)

Por lo tanto, 
 

x = x1 + Dx * t
y = y1 + Dy * t

Tenemos que encontrar (x, y) para t en (0, 1).
Para que x e y sean integrales, Dx y Dy deben ser divisibles por t. Además, t no puede ser irracional ya que Dx y Dy son números enteros.
Por lo tanto, sea t = p / q .
Dx y Dy deben ser divisibles por q. Por lo tanto, GCD de Dx y Dy debe ser q. 
O bien, q = GCD (Dx, Dy).
Solo hay subproblemas más pequeños de GCD (Dx, Dy).
A continuación se muestra la implementación del enfoque anterior: 
 

#include<bits/stdc++.h>
using namespace std;
 
// Function to return the required position
int noOfSquares(int x1, int y1, int x2, int y2)
{
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
 
    int ans = dx + dy - __gcd(dx, dy);
 
    cout<<ans;
}
 
// Driver Code
int main()
{
    int x1 = 1, y1 = 1, x2 = 4, y2 = 3;
 
    noOfSquares(x1, y1, x2, y2);
 
    return 0;
}

// Java program to determine the number
// of squares that line will pass through
class GFG
{
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to return the required position
static void noOfSquares(int x1, int y1,
                        int x2, int y2)
{
    int dx = Math.abs(x2 - x1);
    int dy = Math.abs(y2 - y1);
 
    int ans = dx + dy - __gcd(dx, dy);
 
    System.out.println(ans);
}
 
// Driver Code
public static void main(String []args)
{
    int x1 = 1, y1 = 1, x2 = 4, y2 = 3;
 
    noOfSquares(x1, y1, x2, y2);
}
}
 
// This code contributed by Rajput-Ji

# Python3 program to determine the number
# of squares that line will pass through
from math import gcd
 
# Function to return the required position
def noOfSquares(x1, y1, x2, y2) :
 
    dx = abs(x2 - x1);
    dy = abs(y2 - y1);
 
    ans = dx + dy - gcd(dx, dy);
 
    print(ans);
 
# Driver Code
if __name__ == "__main__" :
 
    x1 = 1; y1 = 1; x2 = 4; y2 = 3;
 
    noOfSquares(x1, y1, x2, y2);
 
# This code is contributed by Ryuga

using System;
 
class GFG
{
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to return the required position
static void noOfSquares(int x1, int y1,
                        int x2, int y2)
{
    int dx = Math.Abs(x2 - x1);
    int dy = Math.Abs(y2 - y1);
 
    int ans = dx + dy - __gcd(dx, dy);
 
    Console.WriteLine(ans);
}
 
// Driver Code
static void Main()
{
    int x1 = 1, y1 = 1, x2 = 4, y2 = 3;
 
    noOfSquares(x1, y1, x2, y2);
}
}
 
// This code is contributed by mits

<?php
// PHP program to determine the number
// of squares that line will pass through
 
// Function to return the required position
function noOfSquares($x1, $y1, $x2, $y2)
{
 
    $dx = abs($x2 - $x1);
    $dy = abs($y2 - $y1);
 
    $ans = $dx + $dy - gcd($dx, $dy);
 
    echo($ans);
}
 
function gcd($a, $b)
{
    if ($b == 0)
        return $a;
    return gcd($b, $a % $b);
     
}
 
// Driver Code
$x1 = 1; $y1 = 1; $x2 = 4; $y2 = 3;
noOfSquares($x1, $y1, $x2, $y2);
 
// This code has been contributed
// by 29AjayKumar
?>

<script>
 
function __gcd(a, b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to return the required position
function noOfSquares(x1, y1, x2, y2)
{
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
 
    var ans = dx + dy - __gcd(dx, dy);
 
    document.write(ans);
}
 
// Driver Code
var x1 = 1, y1 = 1, x2 = 4, y2 = 3;
noOfSquares(x1, y1, x2, y2);
 
// This code is contributed by noob2000.
</script>

4

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)