Encuentre un punto entero en un segmento de línea con dos extremos dados

Dados dos puntos pointU y pointV en el espacio XY, necesitamos encontrar un punto que tenga coordenadas enteras y se encuentre en una línea que pasa por los puntos pointU y pointV. Ejemplos:

If  pointU = (1, -1 and pointV = (-4, 1)
then equation of line which goes 
through these two points is,
2X + 5Y = -3
One point with integer co-ordinate which
satisfies above equation is (6, -3)

Podemos ver que una vez que encontramos la ecuación de la línea, este problema se puede tratar como un problema de algoritmo de Euclides extendido , donde conocemos A, B, C en AX + BY = C y queremos averiguar el valor de X e Y a partir de la ecuacion. En la ecuación de Euclides extendida anterior, C es mcd de A y B, por lo que después de encontrar la ecuación de la línea de dos puntos dados si C no es un múltiplo de mcd (A, B), entonces podemos concluir que no hay una coordenada entera posible en la línea especificada. Si C es un múltiplo de g, podemos aumentar la escala de los coeficientes X e Y encontrados para satisfacer la ecuación real, que será nuestra respuesta final. 

// C++ program to get Integer point on a line
#include <bits/stdc++.h>
using namespace std;
 
// Utility method for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }
 
    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);
 
    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;
 
    return gcd;
}
 
// method prints integer point on a line with two
// points U and V.
void printIntegerPoint(int pointU[], int pointV[])
{
    // Getting coefficient of line
    int A = (pointU[1] - pointV[1]);
    int B = (pointV[0] - pointU[0]);
    int C = (pointU[0] * (pointU[1] - pointV[1]) +
            pointU[1] * (pointV[0] - pointU[0]));
 
    int x, y; // To be assigned a value by gcdExtended()
    int g = gcdExtended(A, B, &x, &y);
 
    // if C is not divisible by g, then no solution
    // is available
    if (C % g != 0)
        cout << "No possible integer point\n";
 
    else
 
        // scaling up x and y to satisfy actual answer
        cout << "Integer Point : " << (x * C/g) << " "
            << (y * C/g) << endl;
}
 
// Driver code to test above methods
int main()
{
    int pointU[] = {1, -1};
    int pointV[] = {-4, 1};
 
    printIntegerPoint(pointU, pointV);
    return 0;
}

// Java program to get Integer point on a line
// Utility method for extended Euclidean Algorithm
class GFG {
 
  public static int x;
  public static int y;
 
  // Function for extended Euclidean Algorithm
  static int gcdExtended(int a, int b)
  {
 
    // Base Case
    if (a == 0) {
      x = 0;
      y = 1;
      return b;
    }
 
    // To store results of recursive call
    int gcd = gcdExtended(b % a, a);
    int x1 = x;
    int y1 = y;
 
    // Update x and y using results of recursive
    // call
    int tmp = b / a;
    x = y1 - tmp * x1;
    y = x1;
 
    return gcd;
  }
 
  // method prints integer point on a line with two
  // points U and V.
  public static void printIntegerPoint(int[] pointU,
                                       int[] pointV)
  {
    // Getting coefficient of line
    int A = (pointU[1] - pointV[1]);
    int B = (pointV[0] - pointU[0]);
    int C = (pointU[0] * (pointU[1] - pointV[1])
             + pointU[1] * (pointV[0] - pointU[0]));
 
    x = 0; // To be assigned a value by gcdExtended()
    y = 0;
    int g = gcdExtended(A, B);
 
    // if C is not divisible by g, then no solution
    // is available
    if (C % g != 0) {
      System.out.print("No possible integer point\n");
    }
 
    else {
 
      // scaling up x and y to satisfy actual answer
      System.out.print("Integer Point : ");
      System.out.print((x * C / g));
      System.out.print(" ");
      System.out.print((y * C / g));
      System.out.print("\n");
    }
  }
 
  // Driver code to test above methods
  public static void main(String[] args)
  {
    int[] pointU = { 1, -1 };
    int[] pointV = { -4, 1 };
 
    printIntegerPoint(pointU, pointV);
  }
}
 
// The code is contributed by phasing17

using System;
 
public static class GFG {
    // C++ program to get Integer point on a line
    // Utility method for extended Euclidean Algorithm
    public static int gcdExtended(int a, int b, ref int x,
                                  ref int y)
    {
        // Base Case
        if (a == 0) {
            x = 0;
            y = 1;
            return b;
        }
 
        int x1 = 0; // To store results of recursive call
        int y1 = 0;
        int gcd = gcdExtended(b % a, a, ref x1, ref y1);
 
        // Update x and y using results of recursive
        // call
        x = y1 - (b / a) * x1;
        y = x1;
 
        return gcd;
    }
 
    // method prints integer point on a line with two
    // points U and V.
    public static void printIntegerPoint(int[] pointU,
                                         int[] pointV)
    {
        // Getting coefficient of line
        int A = (pointU[1] - pointV[1]);
        int B = (pointV[0] - pointU[0]);
        int C = (pointU[0] * (pointU[1] - pointV[1])
                 + pointU[1] * (pointV[0] - pointU[0]));
 
        int x
            = 0; // To be assigned a value by gcdExtended()
        int y = 0;
        int g = gcdExtended(A, B, ref x, ref y);
 
        // if C is not divisible by g, then no solution
        // is available
        if (C % g != 0) {
            Console.Write("No possible integer point\n");
        }
 
        else {
 
            // scaling up x and y to satisfy actual answer
            Console.Write("Integer Point : ");
            Console.Write((x * C / g));
            Console.Write(" ");
            Console.Write((y * C / g));
            Console.Write("\n");
        }
    }
 
    // Driver code to test above methods
    public static void Main()
    {
        int[] pointU = { 1, -1 };
        int[] pointV = { -4, 1 };
 
        printIntegerPoint(pointU, pointV);
    }
}
 
// The code is contributed by Aarti_Rathi

Integer Point : 6 -3

Complejidad temporal: O(logn)
Espacio auxiliar: O(logn)

Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . 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.