Mục tiêu là xác định số ô vuông mà một đường thẳng sẽ đi qua hai điểm cuối đã cho (x1, y1) và (x2, y2).
Để tìm số ô vuông mà đường thẳng của chúng ta đi qua, chúng ta cần tìm:hiệu số giữa các điểm x (dx) =x2-x1, hiệu số giữa các điểm y (dy) =y2-y1, cộng dx và dy và trừ đi gcd của họ (kết quả) =dx + dy - gcd (dx, dy).
Hàm unitSquares (int x1, int y1, int x2, int y2) nhận bốn giá trị x1, y1 và x2, y2. Sự khác biệt tuyệt đối giữa x2 và x1 và sự khác biệt tuyệt đối giữa y2 và y1 được tính. Các dx và dy được cộng và trừ khỏi gcd của dx, dy. Kết quả được lưu trong ans và trả về chính để in.
int unitSquares(int x1, int y1, int x2, int y2){
int dx = abs(x2 - x1);
int dy = abs(y2 - y1);
int ans = dx + dy - __gcd(dx, dy);
return ans;
} Ví dụ
Chúng ta hãy xem cách triển khai sau để xác định số đơn vị diện tích hình vuông mà một đường thẳng sẽ đi qua.
#include<iostream>
#include <algorithm>
using namespace std;
int unitSquares(int x1, int y1, int x2, int y2){
int dx = abs(x2 - x1);
int dy = abs(y2 - y1);
int ans = dx + dy - __gcd(dx, dy);
return ans;
}
int main(){
int x1 = 3, y1 = 3, x2 = 12, y2 = 6;
cout<<"The line passes through "<<unitSquares(x1, y1, x2, y2)<<" squares ";
return 0;
} Đầu ra
Đoạn mã trên sẽ tạo ra kết quả sau -
The line passes through 9 squares