Kiểm tra các điểm có tạo thành đường thẳng C++

Cho danh sách điểm (x, y), kiểm tra xem chúng có thẳng hàng (collinear) hay không.

Thuật toán

Tính độ dốc (slope) giữa 2 điểm đầu: dy/dx = (y1-y0)/(x1-x0). Rút gọn bằng GCD. Kiểm tra tất cả cặp điểm liên tiếp có cùng độ dốc rút gọn không.

Chương trình mẫu

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

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    bool checkStraightLine(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return true;
        
        int dx = points[1][0] - points[0][0];
        int dy = points[1][1] - points[0][1];
        int g = gcd(dx, dy);
        dx /= g; dy /= g; // Độ dốc rút gọn (dx, dy)
        
        for (int i = 2; i < n; i++) {
            int dx2 = points[i][0] - points[i-1][0];
            int dy2 = points[i][1] - points[i-1][1];
            int g2 = gcd(dx2, dy2);
            dx2 /= g2; dy2 /= g2;
            if (dx2 != dx || dy2 != dy) return false;
        }
        return true;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> c = {{1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}};
    cout << (ob.checkStraightLine(c) ? "true" : "false");
    return 0;
}

Kết quả

true

Giải thích: Dùng GCD để chuẩn hóa vector hướng (dx, dy) tránh lỗi chia số thực. So sánh vector hướng của tất cả cặp liên tiếp.

Độ phức tạp: O(n) thời gian, O(1) không gian.

Lưu ý: Xử lý trường hợp dx=0 (đường thẳng đứng) - GCD(0, dy) = |dy|, dx=0, dy=±1.