จำนวนช่องสี่เหลี่ยมหน่วยที่เส้นตรงผ่าน ใน C++

ปัญหา

หาจำนวนช่องสี่เหลี่ยมหน่วย (Unit Squares) ที่เส้นตรงระหว่าง (x1,y1) และ (x2,y2) ผ่าน

สูตร

dx = |x2 - x1|
dy = |y2 - y1|
Answer = dx + dy - gcd(dx, dy)

โปรแกรมตัวอย่าง

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int unitSquares(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    return dx + dy - __gcd(dx, dy);
}

int main() {
    cout << "Squares crossed: " << unitSquares(3, 3, 12, 6);
    return 0;
}

ผลลัพธ์

Squares crossed: 9