Line Problem Solution | CodeChef [Easy]

Problem

A Sniper is standing at the point (x₁, y₁) on the 2D XY Plane. He shoots from his position towards the point (x₂, y₂). Consider the 2D grid formed by integer points on the XY Plane. The position of the Sniper and the Target are lattice points in this grid. The bullet shot by the Sniper will follow a straight line trajectory from (x₁, y₁) to (x₂, y₂). The bullet goes no further than (x₂, y₂).

Example:
Consider the trajectory of the bullet when the Sniper is standing at (1, 1) and the Target lies at (4, 3).

Here, the trajectory of the bullet touches 4 cells. A cell is considered touched by the trajectory if and only if the bullet will enter the cell. How many cells are touched by the trajectory of the bullet?

CodeChef Problem Link

Input

The first line contains a single integer T, the number of test cases. Each of the following T lines contain one test case each. Each test case contains 4 integers x₁, y₁, x₂ and y₂.

Output

For each test case, output a single line, containing the number of cells touched by the trajectory of the bullet shot from (x₁, y₁) to (x₂, y₂).

Constraints

• 0 < T < 10100
• 0 <= x1, y1, x2, y2 ≤ 10^9

Sample Input

3
0 0 3 2
0 0 2 2
0 0 1 0

Sample Output

4
2
0

Solution

Approach: On first look, it seems that answer is the sum of horizontal and vertical distance between (x1, y1) and (x2, y2). However there’s a number of cells which line will not enter and just touch the boundary which is equal to gcd((x2-x1), (y2-y1)).

Code Implementation

//
//  main.cpp
//  Line Problem
//
//  Created by Himanshu on 17/04/22.
//

#include <stdio.h>
#include <math.h>

int gcd (int a, int b) {
    
    if (b == 0) {
        return a;
    } else {
        return gcd(b,a%b);
    }
}


int main() {
    
    int T;
    int x1, y1, x2, y2, gcdNum, ans;

    scanf("%d", &T);

    while (T--) {
        
        scanf("%d %d %d %d",&x1, &y1, &x2, &y2);
        
        if (x2 == x1 || y2 == y1) {
            printf("%d\n",0);
        } else {
            gcdNum = gcd (abs(x2-x1), abs(y2-y1));
            ans = abs(x2-x1) + abs(y2-y1) - gcdNum;
            printf("%d\n",ans);
        }
    }
    
    return 0;
}

Time Complexity: O(logn), where n is the max(x2-x1, y2-y1) and logn is due to the function gcd();