โปรแกรมนับจุดจำนวนเต็มบนเส้นตรงระหว่างสองจุดใน Python

ได้รับสองจุด (p1,q1) และ (p2,q2) ต้องการหาจำนวนจุดที่มีพิกัดเป็นจำนวนเต็มบนเส้นตรงระหว่างสองจุด (ไม่นับจุดปลาย)

ตัวอย่าง: (3,3) ถึง (6,6) → จุด (4,4) และ (5,5) รวม 2 จุด

ขั้นตอนการแก้ปัญหา

จำนวนจุดจำนวนเต็มบนเส้นตรงระหว่างจุด (x1,y1) และ (x2,y2) คือ gcd(|x2-x1|, |y2-y1|) - 1

ตัวอย่างโค้ด Python

def gcd_find(x, y):
    if y == 0:
        return x
    return gcd_find(y, x % y)

def solve(p1, q1, p2, q2):
    return gcd_find(abs(p2 - p1), abs(q2 - q1)) - 1

# ทดสอบ
print(solve(3, 3, 6, 6))  # ผลลัพธ์: 2

อินพุตตัวอย่าง

3,3,6,6

เอาต์พุตตัวอย่าง

2