ตรวจสอบว่าจุดข้อมูลอยู่ในเส้นตรงหรือไม่ใน C++

ปัญหา

ได้รับรายการจุดข้อมูล (x, y) ตรวจสอบว่าจุดเหล่านี้อยู่บนเส้นตรงเดียวกันหรือไม่ เช่น [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)] → อยู่เส้นตรง

วิธีแก้

หาความชัน (Slope) ระหว่างจุดติดกัน เปรียบเทียบว่าทุกคู่มีความชันเท่ากันหรือไม่ ใช้ GCD ลดรูปเศษส่วนเพื่อหลีกเลี่ยง Floating Point

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

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

class Solution {
public:
    int gcd(int a, int b) {
        return !b ? a : gcd(b, a % b);
    }
    bool checkStraightLine(vector<vector<int>>& c) {
        bool ans = true;
        int a = c[1][0] - c[0][0];
        int b = c[1][1] - c[0][1];
        int cc = gcd(a, b);
        a /= cc; b /= cc;
        for (int i = 1; i < c.size(); i++) {
            int x = c[i][0] - c[i-1][0];
            int y = c[i][1] - c[i-1][1];
            int z = gcd(x, y);
            x /= z; y /= z;
            ans = ans && (x == a) && (y == b);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> c = {{1,2},{2,3},{3,4},{4,5},{5,6},{6,7}};
    cout << ob.checkStraightLine(c);
}

อินพุต

[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

เอาต์พุต

1 (1 indicates true)

คำอธิบาย

ใช้ GCD ลดรูป Vector (Δx, Δx) ให้เป็นรูปแบบ Canonical Form แล้วเปรียบเทียบ วิธีนี้แม่นยำกว่าใช้ Floating Point Division

กรณีแนวตั้ง (Δx=0) GCD จะจัดการได้ถูกต้อง (0,1) หรือ (0,-1)