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 Ycoordinates is between Y1 and Y2.
so if we can find a way to quickly count number of horizontal segments in the subset which have Ycoordinates 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 10^{5} + 1 if there’s currently segment intersecting with sweeping line at Ycoordinate 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 Xcoordinates 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 Xcoordinates 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.