PROBLEM LINK:
DIFFICULTY:
Medium
PREREQUISITES:
sweep line, segment tree
PROBLEM:
Given N segments on Cartesian plane, each one is either vertical or horizontal, count the number of intersection points between any pair of the segments.
EXPLANATION:
General explanation
Let’s imagine vertical line moving from very far left (say X=-inf) to very far right (say X=inf) -let’s call this line as “sweeping line”-, at every moment this line is intersecting with some subset of horizontal segments so we can keep track with this subset as long as the sweeping line is moving, now whenever that line meets vertical segment, say it’s endpoints are (X1,Y1) and (X2,Y2) such that X1=X2 and Y1 < Y2, then the answer to its query is the number of horizontal segments which are now intersecting with the sweeping line and their Y-coordinates is between Y1 and Y2.
so if we can find a way to quickly count number of horizontal segments in the subset which have Y-coordinates between any given range then we can answer the query of all vertical segments. however, we also need to support add/erasing segments from the subset.
note that we can do the same idea but with a horizontal sweeping line to answer the queries of horizontal segments.
representing the sweeping line and its movement technically
We want to find a way to store the subset of horizontal segments which are currently interesting with the sweeping line and support quickly adding new segment to this set and support removing existing segment from this set.
This can be done by consider the sweeping line as an array A of length 105 + 1 if there’s currently segment intersecting with sweeping line at Y-coordinate equal to Y then we have A[Y] = 1 otherwise, we have A[Y] = 0, when we want to answer a query to vertical segment then we just need to find the sum of elements in this array inside a given range, so can use segment tree or Fenwick tree data structure.
to simulate the movement of the sweeping line we are only interested in some events that will occur during the movement of the sweeping line which are
-
The sweeping line meets with a vertical segment, because we need to answer its query
-
sweeping line intersect with new horizontal segment
-
sweeping line stop intersecting with a horizontal segment
so we create an array of events that will store all events of any of the above 3 types and sort them according the X-coordinates where it will happen, then we simply do the events in that order.
Corner Cases
- The problem said “at least two other directions to continue their trip” so we should intersecting points that has extensions in 3 or 4 directions but not 2, that means an intersection point can be endpoint of at most of segment but not two, so for simplicity we can include the case that has 2 extensions then exclude them alone, so for now an intersecting can be an endpoint of 2 segments
- when we sort the events in case two or more events have same X-coordinates then we put first events of adding new horizontal segments first, then the events of querying vertical segments and lastly the events of erasing horizontal segments, this is because an intersection point can be an endpoint of a segment.
- also because an intersection point can be an endpoint of a segment, then the range sum query should be inclusive.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
