Dados dos puntos p (x1, y1) y q (x2, y2), calcula el número de puntos integrales que se encuentran en la línea que los une.
Ejemplo: si los puntos son (0, 2) y (4, 0), entonces el número de puntos integrales que se encuentran en él es solo uno y es (2, 1).
De manera similar, si los puntos son (1, 9) y (8, 16), los puntos integrales que se encuentran sobre él son 6 y son (2, 10), (3, 11), (4, 12), (5, 13 ), (6, 14) y (7, 15).
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Enfoque simple
Comience desde cualquiera de los puntos dados, llegue al otro punto final usando bucles. Para cada punto dentro del ciclo, verifica si se encuentra en la línea que une dos puntos dados. En caso afirmativo, aumente la cuenta en 1. La complejidad del tiempo para este enfoque será O(min(x2-x1, y2-y1)).
Enfoque óptimo
1. If the edge formed by joining p and q is parallel
to the X-axis, then the number of integral points
between the vertices is :
abs(p.y - q.y)-1
2. Similarly if edge is parallel to the Y-axis, then
the number of integral points in between is :
abs(p.x - q.x)-1
3. Else, we can find the integral points between the
vertices using below formula:
GCD(abs(p.x - q.x), abs(p.y - q.y)) - 1
¿Cómo funciona la fórmula GCD?
La idea es encontrar la ecuación de la línea en su forma más simple, es decir, en la ecuación ax + by +c, los coeficientes a, b y c se convierten en coprimos. Podemos hacer esto calculando el MCD (máximo común divisor) de a, b y c y convertir a, b y c en la forma más simple.
Entonces, la respuesta será (diferencia de coordenadas y) dividida por (a) – 1. Esto se debe a que después de calcular ax + by + c = 0, para diferentes valores de y, x será el número de valores de y que son exactamente divisibles por una.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ code to find the number of integral points
// lying on the line joining the two given points
#include <iostream>
#include <cmath>
using namespace std;
// Class to represent an Integral point on XY plane.
class Point
{
public:
int x, y;
Point(int a=0, int b=0):x(a),y(b) {}
};
// Utility function to find GCD of two numbers
// GCD of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a%b);
}
// Finds the no. of Integral points between
// two given points.
int getCount(Point p, Point q)
{
// If line joining p and q is parallel to
// x axis, then count is difference of y
// values
if (p.x==q.x)
return abs(p.y - q.y) - 1;
// If line joining p and q is parallel to
// y axis, then count is difference of x
// values
if (p.y == q.y)
return abs(p.x-q.x) - 1;
return gcd(abs(p.x-q.x), abs(p.y-q.y))-1;
}
// Driver program to test above
int main()
{
Point p(1, 9);
Point q(8, 16);
cout << "The number of integral points between "
<< "(" << p.x << ", " << p.y << ") and ("
<< q.x << ", " << q.y << ") is "
<< getCount(p, q);
return 0;
}
Java
// Java code to find the number of integral points
// lying on the line joining the two given points
class GFG
{
// Class to represent an Integral point on XY plane.
static class Point
{
int x, y;
Point(int a, int b)
{
this.x = a;
this.y = b;
}
};
// Utility function to find GCD of two numbers
// GCD of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Finds the no. of Integral points between
// two given points.
static int getCount(Point p, Point q)
{
// If line joining p and q is parallel to
// x axis, then count is difference of y
// values
if (p.x == q.x)
return Math.abs(p.y - q.y) - 1;
// If line joining p and q is parallel to
// y axis, then count is difference of x
// values
if (p.y == q.y)
return Math.abs(p.x - q.x) - 1;
return gcd(Math.abs(p.x - q.x), Math.abs(p.y - q.y)) - 1;
}
// Driver program to test above
public static void main(String[] args)
{
Point p = new Point(1, 9);
Point q = new Point(8, 16);
System.out.println("The number of integral points between "
+ "(" + p.x + ", " + p.y + ") and ("
+ q.x + ", " + q.y + ") is "
+ getCount(p, q));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 code to find the number of
# integral points lying on the line
# joining the two given points
# Class to represent an Integral point
# on XY plane.
class Point:
def __init__(self, a, b):
self.x = a
self.y = b
# Utility function to find GCD
# of two numbers GCD of a and b
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# Finds the no. of Integral points
# between two given points.
def getCount(p, q):
# If line joining p and q is parallel
# to x axis, then count is difference
# of y values
if p.x == q.x:
return abs(p.y - q.y) - 1
# If line joining p and q is parallel
# to y axis, then count is difference
# of x values
if p.y == q.y:
return abs(p.x - q.x) - 1
return gcd(abs(p.x - q.x),
abs(p.y - q.y)) - 1
# Driver Code
if __name__ == "__main__":
p = Point(1, 9)
q = Point(8, 16)
print("The number of integral points",
"between ({}, {}) and ({}, {}) is {}" .
format(p.x, p.y, q.x, q.y, getCount(p, q)))
# This code is contributed by Rituraj Jain
C#
// C# code to find the number of integral points
// lying on the line joining the two given points
using System;
class GFG
{
// Class to represent an Integral point on XY plane.
public class Point
{
public int x, y;
public Point(int a, int b)
{
this.x = a;
this.y = b;
}
};
// Utility function to find GCD of two numbers
// GCD of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Finds the no. of Integral points between
// two given points.
static int getCount(Point p, Point q)
{
// If line joining p and q is parallel to
// x axis, then count is difference of y
// values
if (p.x == q.x)
return Math.Abs(p.y - q.y) - 1;
// If line joining p and q is parallel to
// y axis, then count is difference of x
// values
if (p.y == q.y)
return Math.Abs(p.x - q.x) - 1;
return gcd(Math.Abs(p.x - q.x), Math.Abs(p.y - q.y)) - 1;
}
// Driver code
public static void Main(String[] args)
{
Point p = new Point(1, 9);
Point q = new Point(8, 16);
Console.WriteLine("The number of integral points between "
+ "(" + p.x + ", " + p.y + ") and ("
+ q.x + ", " + q.y + ") is "
+ getCount(p, q));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// javascript code to find the number of integral points
// lying on the line joining the two given points
// Class to represent an Integral point on XY plane.
class Point {
constructor(a , b) {
this.x = a;
this.y = b;
}
}
// Utility function to find GCD of two numbers
// GCD of a and b
function gcd(a , b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Finds the no. of Integral points between
// two given points.
function getCount( p, q)
{
// If line joining p and q is parallel to
// x axis, then count is difference of y
// values
if (p.x == q.x)
return Math.abs(p.y - q.y) - 1;
// If line joining p and q is parallel to
// y axis, then count is difference of x
// values
if (p.y == q.y)
return Math.abs(p.x - q.x) - 1;
return gcd(Math.abs(p.x - q.x), Math.abs(p.y - q.y)) - 1;
}
// Driver program to test above
p = new Point(1, 9);
q = new Point(8, 16);
document.write("The number of integral points between " + "(" + p.x + ", " + p.y + ") and (" + q.x + ", "
+ q.y + ") is " + getCount(p, q));
// This code is contributed by gauravrajput1
</script>
Producción:
The number of integral points between (1, 9) and (8, 16) is 6
Complejidad de tiempo: O(log(min(a,b))), ya que estamos usando la recursividad para encontrar el GCD.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Referencia:
https://www.geeksforgeeks.org/count-integral-points-inside-a-triangle/
Este artículo ha sido aportado por Paridhi Johari. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA