Number of Integral Points In a Line

/// Reference : https://bit.ly/2J7iFe3

Let’s our starting co-ordinate - A [ x1, y1 ] <-> [ 3, 17 ] and

ending co-ordinate - B [ x2, y2 ] <-> [ 48, 281 ] .

We have to find the number of integral co-ordinates which lies on this line (AB) joining two co-ordinates .So , our equation of this line will be ( suppose a new co-ordinate on this line is [ x , y ] )

(x−x1)/(y−y1)=(x1−x2)/(y1−y2) 

(x−3)/(y−17)=(−45)/(−264) 

(x−3)/(y−17)=(45/264) 

(x)=(45/264)∗(y−17)+3 

(x)=(15/88)∗(y−17)+3...(1)[(45/264)=(15/88)] 

According to the same way →  (y)=(88/15)∗(x−3)+17...(2) 

So , now from our calculation - every co-ordinate which lies on this line (AB) will satisfy our above equation ……………..

So , x of the new point on line (AB) will be our valid integer ….( 1 )

1.if and only if (y-17) is multiple of 88

2.x will be in the range [ 3, 48 ] , won't it ??

So y of the new point on line ( A B) will be our valid integer …… ( 2 )

1.if and only if (x-3) is multiple of 15

2.y will be in the range [ 17, 281 ] , won’t it ??

Now let’s look at there are only 4 multiples of 15 for which equation (2) will be satisfied and y will be in range [17, 281] The values of x ,

3 , 18 , 33, 48 for them the value of y will be

17 , 105 , 193 , 281

if we see for equation no. (1) Then by completing all validation , there will be also four values possible …………..Actually this is = the gcd of the value  (45,264)+1. 

From the equation , we know

(x-3) / (y-17) = (45 /264)= ( 15 * 3 / 88 * 3 )

So the possible integral values of the ( x-3 ) and ( y-17 ) will maintain ratio same and not crossing the limit of x (45) and y(264) . So obviously the possible values will be gcd(45,264)= 3=3 .

15*1 / 88* 1 = 15*2 / 88*2 = 15*3 / 88*3

So ans is gcd( ( x1-x2) , (y1-y2) ) +1 . 

#include<bits/stdc++.h>

using namespace std;

int gcd(int a, int b)

{

if(b == 0)

return a;

return gcd(b, a%b);

}

int main()

{

int x1, y1, x2, y2;

cout << "Enter x1 and y1 :: ";

cin >> x1 >> y1;

cout << "\nEnter x2 and y2 :: ";

cin >> x2 >> y2;

int r1 = abs(x1-x2);

int r2 = abs(y1-y2);

int ans = gcd(r1, r2) + 1;

cout << "\nNumber of integral points :: " << ans << "\n";

return 0;

}