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.

Examples:

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.

`// 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` `c[], ` `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 divisble by g, then no solution ` ` ` `// is available ` ` ` `if` `(C % g != 0) ` ` ` `cout << ` ```
"No possible integer point
"
``` `; ` ` ` ` ` `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; ` `} ` |

Output:

Integer Point : 6 -3

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments