Grid Points on a Segment

Difficulty: 1300 2000 ms 128 MB

math geometry

How many lattice (integer-coordinate) points lie on the closed segment from (x1, y1) to (x2, y2)?

Input: one line with four integers x1 y1 x2 y2.

Output: gcd(|Δx|, |Δy|) + 1.

Constraints:

• |coordinates| ≤ 10⁹

Sample Tests

0 0 6 4

3

1 1 1 1

1

Read the Editorial