Kiểm tra 3 điểm thẳng hàng (Collinear) trong C++

Ba điểm A(x1,y1), B(x2,y2), C(x3,y3) thẳng hàng (collinear) khi diện tích tam giác chúng tạo thành bằng 0.

Công thức diện tích

Area = 0.5 * | x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) |

Nếu Area == 0 → 3 điểm thẳng hàng. Tránh dùng float so sánh chính xác bằng 0 → dùng cross product (tích chéo) số nguyên.

Phương pháp Cross Product (Khuyên dùng)

Vector AB = (x2-x1, y2-y1), AC = (x3-x1, y3-y1).
cross = AB.x * AC.y - AB.y * AC.x.
Nếu cross == 0 → thẳng hàng.

Chương trình C++ hoàn chỉnh

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

bool areCollinear(long long x1, long long y1,
                  long long x2, long long y2,
                  long long x3, long long y3) {
    // Cross product của AB và AC
    long long cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    return cross == 0;
}

int main() {
    // Test cố định
    cout << "Test 1: (0,0), (1,1), (2,2) -> " 
         << (areCollinear(0,0, 1,1, 2,2) ? "Thang hang" : "Khong thang hang") << '\n';
    cout << "Test 2: (0,0), (1,1), (2,3) -> " 
         << (areCollinear(0,0, 1,1, 2,3) ? "Thang hang" : "Khong thang hang") << '\n';
    cout << "Test 3: (1,2), (3,4), (5,6) -> " 
         << (areCollinear(1,2, 3,4, 5,6) ? "Thang hang" : "Khong thang hang") << '\n';
    
    // Test ngẫu nhiên
    srand(time(0));
    const int L = 1, U = 20;
    cout << "\n--- 5 test ngau nhien ---\n";
    for (int t = 0; t < 5; ++t) {
        long long x1 = rand() % (U-L+1) + L;
        long long y1 = rand() % (U-L+1) + L;
        long long x2 = rand() % (U-L+1) + L;
        long long y2 = rand() % (U-L+1) + L;
        long long x3 = rand() % (U-L+1) + L;
        long long y3 = rand() % (U-L+1) + L;
        
        cout << "(" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ") (" << x3 << "," << y3 << ") -> "
             << (areCollinear(x1,y1,x2,y2,x3,y3) ? "Thang hang" : "Khong thang hang") << '\n';
    }
    return 0;
}

Kết quả mẫu

Test 1: (0,0), (1,1), (2,2) -> Thang hang
Test 2: (0,0), (1,1), (2,3) -> Khong thang hang
Test 3: (1,2), (3,4), (5,6) -> Thang hang

--- 5 test ngau nhien ---
(12,5) (7,18) (3,9) -> Khong thang hang
(4,4) (8,8) (12,12) -> Thang hang
(2,15) (10,5) (18,20) -> Khong thang hang
(5,5) (5,10) (5,15) -> Thang hang (trung tuyen doc)
(1,1) (20,20) (10,10) -> Thang hang

Phương pháp thay thế: Diện tích (dùng double)

double area = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
if (area < 1e-9) // Giả sử bằng 0

Nhược điểm: Sai số làm tròn float, chậm hơn integer cross product.

Mở rộng: Kiểm tra nhiều điểm thẳng hàng

Cho N điểm, kiểm tra có K điểm bất kỳ thẳng hàng không → O(N^2 log N) bằng cách gom nhóm theo góc (slope) từ mỗi điểm.

Ứng dụng

• Computer graphics: phát hiện đường thẳng, đơn giản hóa polyline (Ramer-Douglas-Peucker).
• Computational geometry: Convex hull (Graham scan loại bỏ điểm thẳng hàng).
• Robotics: Kiểm tra va chạm, path planning.
• Image processing: Hough transform phát hiện đường thẳng.

Lưu ý

• Dùng long long (64-bit) để tránh tràn số khi tọa độ lớn (≤ 10^9).
• Cross product = 0 cũng bao gồm trường hợp 2 điểm trùng nhau (vector độ dài 0).
• Nếu cần loại trừ điểm trùng, kiểm tra thêm (x1==x2 && y1==y2) || ....

Cross product là công cụ mạnh mẽ, gọn nhẹ cho nhiều bài toán hình học phẳng.