📜 Mô tả bài toán

Cho \(N\) đoạn thẳng trong mặt phẳng tọa độ 2D. Mỗi đoạn song song với trục hoành (OX) hoặc trục tung (OY). Hai đoạn thẳng được coi là cắt nhau nếu chúng có một điểm chung (bao gồm cả điểm đầu/mút).

Yêu cầu: Đếm số cặp đoạn thẳng cắt nhau.

Ràng buộc:

• \(2 \le N \le 2 \times 10^5\)
• Tọa độ các điểm có giá trị tuyệt đối không quá \(10^9\)
• Không có đoạn chéo. Chỉ có đoạn ngang (OX) hoặc dọc (OY)

💡 Ý tưởng giải

Nhận xét quan trọng:

• Hai đoạn cùng phương (cùng song song OX hoặc OY) không bao giờ cắt nhau.
• Chỉ những đoạn ngang (song song OX) và dọc (song song OY) mới có thể cắt nhau tại một điểm chung.

Chiến lược:

Ta sẽ dùng sweep line theo trục OX:

• Duyệt theo thứ tự tăng dần của hoành độ X.
• Khi gặp đoạn ngang:
  • Tạo 2 event:
    • Bắt đầu tại x1, thêm đoạn ngang vào hệ thống tại hoành độ x1, tung độ y.
    • Kết thúc tại x2 + 1, xóa đoạn ngang khỏi hệ thống.
• Khi gặp đoạn dọc tại x:
  • Kiểm tra tại thời điểm x, có bao nhiêu đoạn ngang đang "sống" và có tung độ nằm trong đoạn [y1, y2].

Cấu trúc dữ liệu hỗ trợ:

• Dùng Fenwick Tree (BIT) để hỗ trợ cộng/trừ và truy vấn số lượng đoạn ngang theo tung độ y.
• Vì giá trị y rất lớn (\(\pm 10^9\)), ta cần compress (nén) toàn bộ các giá trị y thành các chỉ số nhỏ hơn (1..k).

✍️ Ví dụ minh họa

Input:

3
-2 0 2 0
-1 0 1 0
0 -1 0 1

• Đoạn 1 và 2: ngang (OX), y = 0
• Đoạn 3: dọc (OY), x = 0, từ y = -1 đến 1

Phân tích:

• Đoạn dọc tại x = 0 cắt 2 đoạn ngang y = 0 → Kết quả: 2

🧮 Độ phức tạp

• Nén tọa độ Y: O(N log N)
• Sort events: O(N log N)
• Xử lý các event: O(N log N) với BIT

➡️ Tổng: O(N log N) — đủ nhanh cho \(N \le 2 \times 10^5\)

💻 Code minh họa (C++)

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

const int N = 4e5 + 5;

struct event {
    int x, Ly, Ry, type;
    bool operator < (const event &other) const {
        if (x == other.x) return type < other.type;
        return x < other.x;
    }
};

int numSegment, ft[N];
long long res = 0;
vector<event> Events;
vector<int> compressOy;

void update(int x, int val) {
    for(; x < N; x += x & -x) ft[x] += val;
}

int getSum(int x) {
    int ans = 0;
    for(; x; x -= x & -x) ans += ft[x];
    return ans;
}

int get(int l, int r) {
    return getSum(r) - getSum(l - 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> numSegment;
    for(int i = 0; i < numSegment; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) {
            if (y1 > y2) swap(y1, y2);
            Events.push_back({x1, y1, y2, 2}); // vertical
        } else {
            if (x1 > x2) swap(x1, x2);
            Events.push_back({x1, y1, y1, 1});    // horizontal open
            Events.push_back({x2 + 1, y1, y1, -1}); // horizontal close
        }
        compressOy.push_back(y1);
        compressOy.push_back(y2);
    }

    sort(Events.begin(), Events.end());
    sort(compressOy.begin(), compressOy.end());
    compressOy.resize(unique(compressOy.begin(), compressOy.end()) - compressOy.begin());

    for(auto &e : Events) {
        e.Ly = lower_bound(compressOy.begin(), compressOy.end(), e.Ly) - compressOy.begin() + 1;
        e.Ry = lower_bound(compressOy.begin(), compressOy.end(), e.Ry) - compressOy.begin() + 1;
    }

    for(auto e : Events) {
        if (e.type == 2) res += get(e.Ly, e.Ry);
        else update(e.Ly, e.type);
    }

    cout << res;
    return 0;
}

🏁 Kết luận

Đây là một bài toán điển hình áp dụng kỹ thuật sweep line + BIT/Fenwick Tree, kết hợp với coordinate compression để xử lý lượng dữ liệu lớn. Bài toán củng cố kỹ năng xử lý hình học cơ bản và thuật toán trên cấu trúc dữ liệu hiệu quả.