Tìm giao điểm của các đường thẳng trong đoạn dọc trong C++

Cho tập hợp các đường thẳng dạng y = mx + c và một đoạn dọc từ x = left đến x = right. Kiểm tra xem có giao điểm nào của hai đường thẳng nằm trong đoạn dọc này hay không. Ví dụ: L1: y = x+2, L2: y = -x+7, L3: y = -3, L4: y = 2x-7. Đoạn dọc x ∈ [2, 4]. Giao điểm của L1 và L2 nằm trong đoạn này.

Giải thuật sắp xếp

1. Tính tọa độ y của giao điểm mỗi đường thẳng với hai biên left và right.
2. Lưu lại dưới dạng cặp (y_left, y_right).
3. Sắp xếp các cặp theo y_left tăng dần.
4. Duyệt qua các cặp liên tiếp. Nếu y_right của cặp sau nhỏ hơn cặp trước, tồn tại giao điểm trong đoạn.

Ví dụ minh họa

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

struct Line {
    int slope, intercept;
    Line(int m=0, int c=0) : slope(m), intercept(c) {}
};

int getY(Line l, int x) {
    return l.slope * x + l.intercept;
}

bool hasIntersection(Line lines[], int left, int right, int n) {
    pair borders[100];
    for (int i = 0; i < n; i++)
        borders[i] = {getY(lines[i], left), getY(lines[i], right)};
    
    sort(borders, borders + n);
    
    for (int i = 1; i < n; i++)
        if (borders[i].second < borders[i-1].second)
            return true;
    return false;
}

int main() {
    Line lines[4] = {{1,2}, {-1,7}, {0,-3}, {2,-7}};
    int left = 2, right = 4;
    
    if (hasIntersection(lines, left, right, 4))
        cout << "Giao điểm nằm giữa " << left << " và " << right;
    else
        cout << "Không có giao điểm trong đoạn";
    return 0;
}

Kết quả

Giao điểm nằm giữa 2 và 4