Sweep Line Algorithms

C++ — sweep line pattern

struct Event {
    double x;
    int type;  // +1 for segment start, -1 for end
    int id;
};

vector events;
for (int i = 0; i < n; i++) {
    events.push_back({segments[i].l.x, 1, i});
    events.push_back({segments[i].r.x, -1, i});
}
sort(events.begin(), events.end(), [](auto& a, auto& b) {
    return a.x < b.x;
});

// Active set: ordered by current y at sweep position
// For each start event, check against active segments
// For each end event, remove from active set
// O((N+K) log N) for K intersections