how to solve this

general
1

Can anyone explain me how to solve this problem with the help of an example

2

Its really simple.

Let dx = abs(x1-x2), dy = (y1 - y2).

If dx == dy, answer is dx. Example (1,1),(4,4) ans = 3.

Else take gcd of dx and dy, lets it be gcd and divide both dx and dy by gcd.

This gcd means the number of times a line crosses through integer coordinates +1.

For example:- (1,1) and (7,5)

Dx = 6, dy = 4. Gcd = 2.

If we plot this line on graph, we will see that line passes through only integer coordinates once, at (4,3).

Also, note that we can split this problems into sub problems, just see that count of grid squares, intersecting line is
Same from (1,1),(4,3) as between (4,3) and (7,5).

So, we can simply solve this problem for dx/gcd and dy/ gcd and multiply final ans by gcd.

Now, solving for smallest rectangle (1,1) and (4,3), just plot this line on graph and count number of times the line crosses a grid line. (Grid line of graph).

You will note that line crosses grid lines parallel to x-axis dy-1 times and grid lines parallel to y-axis dx-1 times.

Also, every time we cross a grid line, we enter a new grid square.

So count of grid squares through which line passes through in smallest problem is dx-1 + dy - 1 +1.

We added 1, because we didnt added the first square in this process.

So, final ans = (dx/gcd + dy/gcd -1)*gcd

PS: have look at editorial too…

2 Likes
3

laddus removed but then also you are there for help you are great @taran_1407

4

Accepting that with a bow…

No problem…

1 Like