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 explanationLet'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 technicallyWe 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
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
SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '16, 10:41

Hi Can someone explain the reason why my (brute force) code gives WA for subtask 1 (for subtask 2, it would definitely give TLE)? I checked all line segments pairwise and if they had any valid intersection, I incremented the total count and also the count for the respective line segments. Where is it going wrong? Code link: solution answered 16 Nov '16, 18:51
Your solution fails for the test case: 2 1 2 3 2 2 1 2 2 The answer must be: 1 1 1 Your answer is: 0 0 0 The figure is in the form of the alphabet "T". Happy coding ;)
(16 Nov '16, 23:09)

There's a typo, one of the two "sweeping line intersect with new horizontal segment" should be "sweeping line intersect with end of horizontal segment". In short, given a vertical segment from (x,y1) to (x,y2) y2>y1, events to be determined are
answered 17 Nov '16, 11:03
