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