Hướng giải của Giao điểm đoạn thẳng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Dùng thuật toán đường quét (Bentley-Ottmann) kiểm tra giao điểm hai đoạn thẳng. Vì chỉ cần kiểm tra sự tồn tại giao điểm, ta có thể dùng phương pháp đơn giản hơn: sắp xếp các đầu mút theo toạ độ \(x\), duy trì một cấu trúc dữ liệu (như set) chứa các đoạn đang xét theo thứ tự toạ độ \(y\), và kiểm tra giao điểm giữa các đoạn liền kề trong cấu trúc đó.

Hàm xác định hướng quay (cross product) và hàm kiểm tra giao điểm (segment intersection) được sử dụng để quyết định hai đoạn có cắt nhau không.

Độ phức tạp: \(O(N \log N)\).

Mã nguồn C++

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

struct Point {
    long long x, y;
    Point() {}
    Point(long long x, long long y) : x(x), y(y) {}
};

struct Segment {
    Point p, q;
    int id;
    Segment() {}
    Segment(Point p, Point q, int id) : p(p), q(q), id(id) {}
};

long long cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool onSegment(const Point& p, const Point& a, const Point& b) {
    if (cross(a, b, p) != 0) return false;
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool intersect(const Segment& s1, const Segment& s2) {
    long long o1 = cross(s1.p, s1.q, s2.p);
    long long o2 = cross(s1.p, s1.q, s2.q);
    long long o3 = cross(s2.p, s2.q, s1.p);
    long long o4 = cross(s2.p, s2.q, s1.q);
    if (((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0)) &&
        ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0))) return true;
    if (o1 == 0 && onSegment(s2.p, s1.p, s1.q)) return true;
    if (o2 == 0 && onSegment(s2.q, s1.p, s1.q)) return true;
    if (o3 == 0 && onSegment(s1.p, s2.p, s2.q)) return true;
    if (o4 == 0 && onSegment(s1.q, s2.p, s2.q)) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<Segment> segs(n);
    for (int i = 0; i < n; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segs[i] = Segment(Point(x1, y1), Point(x2, y2), i);
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (intersect(segs[i], segs[j])) {
                cout << "1\n";
                return 0;
            }
    cout << "0\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.