Số ô vuông đơn vị đường thẳng đi qua (Line through Grid Squares) trong C++

Cho hai điểm (x1, y1) và (x2, y2) trên lưới ô vuông đơn vị. Tính số ô vuông mà đoạn thẳng nối hai điểm cắt qua (cắt nội tâm, không chỉ chạm đỉnh/góc).

Công thức toán học

Kết quả = |x2 - x1| + |y2 - y1| - gcd(|x2 - x1|, |y2 - y1|)

Chứng minh: Đường thẳng cắt qua dx đường dọc và dy đường ngang. Tại các điểm giao cắt của đường dọc và ngang (đỉnh lưới), đường thẳng đi qua một đỉnh chung -> giảm 1 ô so với việc cộng riêng. Số đỉnh lưới trên đoạn thẳng (trừ 2 đầu) = gcd(dx, dy) - 1. Tổng ô = dx + dy - gcd(dx, dy).

Ví dụ

Điểm (3, 3) -> (12, 6). dx = 9, dy = 3. gcd(9, 3) = 3.

Số ô = 9 + 3 - 3 = 9.

Chương trình C++

#include <iostream>
#include <algorithm> // std::gcd (C++17)
#include <cstdlib>   // abs
using namespace std;

int squaresCrossed(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    if (dx == 0 && dy == 0) return 0;
    int g = std::gcd(dx, dy);
    return dx + dy - g;
}

int main() {
    int x1 = 3, y1 = 3, x2 = 12, y2 = 6;
    cout << "Doan thang (" << x1 << "," << y1 << ") -> (" << x2 << "," << y2 << ")" << endl;
    cout << "dx=" << abs(x2-x1) << ", dy=" << abs(y2-y1) << ", gcd=" << std::gcd(abs(x2-x1), abs(y2-y1)) << endl;
    cout << "So o vuong don vi cat qua: " << squaresCrossed(x1, y1, x2, y2) << endl;
    return 0;
}

Đầu ra

Doan thang (3,3) -> (12,6)
dx=9, dy=3, gcd=3
So o vuong don vi cat qua: 9