Kiểm tra các điểm có nằm trên hai đường thẳng song song C++

Cho mảng arr, điểm thứ i có tọa độ (i, arr[i]). Kiểm tra xem có thể vẽ 2 đường thẳng song song chứa tất cả các điểm không.

Ý tưởng

• Hai đường thẳng song song → cùng hệ số góc (slope).
• Chọn 3 điểm đầu tiên, trong đó ít nhất 2 điểm nằm trên cùng 1 đường → 3 trường hợp slope.
• Với mỗi slope thử, tính đoạn chặn (intercept) của mọi điểm. Nếu chỉ có đúng 2 giá trị intercept phân biệt → thỏa mãn.

Chương trình C++

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

bool checkIntercept(double slope, const vector<int>& arr) {
    set<double> intercepts;
    for (int i = 0; i < (int)arr.size(); i++)
        intercepts.insert(arr[i] - slope * i);
    return intercepts.size() == 2;
}

bool isParallel(const vector<int>& arr) {
    int n = arr.size();
    if (n < 3) return true;
    // 3 trường hợp slope từ 3 điểm đầu
    double s1 = arr[1] - arr[0];
    double s2 = arr[2] - arr[1];
    double s3 = (arr[2] - arr[0]) / 2.0;
    return checkIntercept(s1, arr) || checkIntercept(s2, arr) || checkIntercept(s3, arr);
}

int main() {
    vector<int> arr = {2, 6, 8, 12, 14};
    cout << (isParallel(arr) ? "1" : "0") << "\n"; // 1 = Có thể
    return 0;
}

Kết quả

1

Giải thích: Đường 1 qua (1,2),(3,8),(5,14) slope=3. Đường 2 qua (2,6),(4,12) slope=3. Hai đường song song.