Given two points pointU and pointV in XY-space, we need to find a point which has integer coordinates and lies on a line going through points pointU and pointV.
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)
We can see that once we found the equation of line, this problem can be treated as Extended Euclid algorithm problem, where we know A, B, C in AX + BY = C and we want to find out the value of X and Y from the equation.
In above Extended Euclid equation, C is gcd of A and B, so after finding out the line equation from given two points if C is not a multiple of gcd(A, B) then we can conclude that there is no possible integer coordinate on the specified line. If C is a multiple of g, then we can scale up the founded X and Y coefficients to satisfy the actual equation, which will be our final answer.
Integer Point : 6 -3
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.