Số tam giác từ giao điểm đoạn thẳng ngang/dọc C++

Cho tập đoạn thẳng ngang và dọc. Tìm số tam giác tạo thành từ các điểm giao nhau.

Thuật toán Sweep Line + BIT (Fenwick Tree)

• Sự kiện: đầu/cuối đoạn ngang, đoạn dọc (query).
• Quét theo trục x, dùng BIT trên trục y để đếm đoạn ngang đang hoạt động.
• Mỗi đoạn dọc query số đoạn ngang cắt nó → số giao điểm.
• Số tam giác = C(điểm_giao, 3).

Chương trình C++

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

const int MAXY = 1000005;
int BIT[MAXY];

void update(int idx, int val) {
    for (; idx < MAXY; idx += idx & -idx) BIT[idx] += val;
}
int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) res += BIT[idx];
    return res;
}

struct Event {
    int x, y1, y2, type; // type: 1=start horiz, 2=end horiz, 3=vertical
    bool operator<(Event const& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type; // start(1) < vertical(3) < end(2)
    }
};

int main() {
    vector events;
    auto addHoriz = [&](int x1, int x2, int y) {
        if (x1 > x2) swap(x1, x2);
        events.push_back({x1, y, 0, 1});
        events.push_back({x2, y, 0, 2});
    };
    auto addVert = [&](int x, int y1, int y2) {
        if (y1 > y2) swap(y1, y2);
        events.push_back({x, y1, y2, 3});
    };
    
    // Ví dụ đầu vào
    addVert(3, 2, 13);
    addHoriz(1, 3, 5);
    addVert(8, 2, 8);
    addHoriz(3, 6, 4);
    addVert(4, 3, 5);
    
    sort(events.begin(), events.end());
    
    long long intersections = 0;
    for (auto &e : events) {
        if (e.type == 1) update(e.y1, 1);
        else if (e.type == 2) update(e.y1, -1);
        else intersections += query(e.y2) - query(e.y1 - 1);
    }
    
    long long triangles = (intersections >= 3) ? intersections * (intersections-1) * (intersections-2) / 6 : 0;
    cout << "Giao diem: " << intersections << "\n";
    cout << "So tam giac: " << triangles << "\n";
    return 0;
}

Kết quả

Giao diem: 3
So tam giac: 1