Số điểm nguyên giữa hai điểm C++

Tìm số điểm nguyên nằm giữa hai điểm cho trước.

Công thức: gcd(|x1-x2|, |y1-y2|) - 1. Nếu song song trục x: |y1-y2|-1. Nếu song song trục y: |x1-x2|-1.

Ví dụ: (1,5), (1,3) → 1 điểm.

Giải thuật

• Hàm gcd(a, b)
• Nếu x1==x2: trả về |y1-y2|-1
• Nếu y1==y2: trả về |x1-x2|-1
• Ngược lại: gcd(|x1-x2|, |y1-y2|) - 1

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

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

int getCount(int pointOne[], int pointTwo[]) { 
    if (pointOne[0] == pointTwo[0]) 
        return abs(pointOne[1] - pointTwo[1]) - 1; 
    if (pointOne[1] == pointTwo[1]) 
        return abs(pointOne[0] - pointTwo[0]) - 1; 
    return gcd(abs(pointOne[0] - pointTwo[0]), abs(pointOne[1] - pointTwo[1])) - 1; 
} 

int main() { 
    int pointOne[] = {1, 3}, pointTwo[] = {10, 12}; 
    cout << getCount(pointOne, pointTwo) << endl; 
    return 0; 
} 

Đầu ra

8