I found an algorithm similar to the one posted by John, but with lower complexity.
First start by creating a comparator for the segment. This comparator is only used for the sweep line and doesn't work elsewhere, i.e. doesn't give you an actual topological order, but does give you a "partial" (?) order during the sweep line. This exploits the fact that during the sweep line, the segment events enter in order from left to right.
struct Segment {
Point p, q; // endpoints
// "to_vec()" transforms the segment to a vector
// "^" is the operator for cross product.
// "to" creates a vector from A to B
bool operator<(const Segment& s) const {
if (p.x < s.p.x) {
// "this" enters first (in the sweep line)
return (to_vec() ^ p.to(s.p)) < 0;
} else {
// "this" enters after the one being compared
return (s.to_vec() ^ s.p.to(p)) > 0;
}
}
}
Then the sweep line.
Before starting, sort the segments by ascending X coordinate (only left endpoint). Then, assign an idx
(index) starting from 0 to each segment. This must be done after sorting for the following code to work properly.
I explain the sweep line in the comments:
typedef pair<int, int> pii;
// ....
// Sort segments by left endpoint X
sort(segments.begin(), segments.end(),
[](const Segment& a, const Segment& b) { return a.p.x < b.p.x; });
// Create a graph with the same amount of segments +1.
// The last node will be used for a imaginary node that's the
// starting point (i.e. imagine it coming from Y=infinite above)
vector<vector<int>> graph(N + 1);
// Assign an ID to each segment
for (int i = 0; i < N; i++) segments[i].idx = i;
// Create a Segment set. Starts empty.
// Note that this is a set with order (tree set)
set<Segment> s;
// Create a priority queue containing integer pairs.
// Order of the queue is ascending.
priority_queue<pii, vector<pii>, greater<pii>> events;
// For every segment
for (int i = 0; i < N; i++) {
// Iterate through all the events in the priority queue until
// the X value in the queue becomes higher than the current left endpoint
// X value. In other words consume all values that are to the left of the
// current segment. Delete them from the set as well as from the queue.
while (!events.empty() && events.top().first < segments[i].p.x) {
s.erase(segments.at(events.top().second));
events.pop();
}
// Insert the segment in the set. This order won't be topological,
// but it's enough for the current sweep line state.
auto it = s.insert(segments[i]).first;
// If the segment inserted is the first one in the set, then add it
// to the imaginary node. Else add it to the previous one.
// This is the step that gets faster than the algorithm of the accepted
// answer, since we can find where to insert it in just one O(log N) step,
// without caring how many covered segments there are.
if (it == s.begin())
graph[N].push_back(i);
else
graph.at((--it)->idx).push_back(i);
// Insert the right endpoint X to the priority queue along with the current
// segment index.
events.push({segments[i].q.x, i});
}
Also it seems that idx
must be set to each segment after sorting. By doing this, when doing the toposort it will deal with some corner cases such as:
Segment 1 enters the vertical sweep line. It's not covered, so it's parent in the DAG is the extra imaginary node.
Segment 2 enters the vertical sweep line and it covers 1. It's not covered, so it's parent is the extra imaginary node.
But we didn't set segment 2 to be parent of segment 1. However, there's no problem, because when doing the toposort, and if we do it in the correct order, the post order traversal will be 1 2 0 (zero being the extra node), so we invert the array and remove the first element, becoming 2 1, which means that the segment 2 does cover 1 (although it may not necessarily cover it in some situations).
In other words, with this approach the resulting graph will have some edges "missing", but when you do the toposort, the segments which left endpoint X coordinate is higher will appear first in the toposort result anyway, so the missing edges don't matter.
UPDATE: My code is here:
https://github.com/ChrisVilches/Algorithms/blob/main/spoj/RAIN1-november_rain.cpp
I refactored it a bit, so it's slightly different from annotated code I wrote above (for example instead of assigning a idx
property, I just use the actual index in the array, and pass it to the set grouped as a pair<Segment, int>
). Take a look at the vector<Segment> sort_segments(vector<Segment>& segments)
method (also the struct
s and toposort
are of interest, maybe).
This program solves the November Rain problem (https://www.spoj.com/problems/RAIN1/) which only has 40,000 segments and at most 25 segments being covered at each X coordinate, so a slower algorithm works. But there's a more complicated problem called Directing Rainfall (https://open.kattis.com/problems/directingrainfall - I haven't solved it yet) which requires a similar algorithm, but does not have any limit for how many segments are covered. I learnt this algorithm by checking some existing solutions to that last problem.
Alternative implementation:
A different implementation done by adding two events per each segment (enter and exit). The only problem is that there's a corner case for when there are two segments with endpoints with equal X coordinate, so I added +1 to the exiting coordinate. The previous implementation using a priority queue is safer, since it doesn't need to deal with this corner case.
set<pair<Segment, int>> s;
vector<tuple<ll, bool, int>> events;
for (int i = 0; i < N; i++) {
events.push_back({segments[i].p.x, true, i});
events.push_back({segments[i].q.x + 1, false, i});
}
sort(events.begin(), events.end());
for (const auto& [_, enter, idx] : events) {
if (enter) {
const auto it = s.insert({segments[idx], idx}).first;
graph[it == s.begin() ? N : prev(it)->second].push_back(idx);
} else {
s.erase({segments[idx], idx});
}
}