 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.

1 Like

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?

Your solution fails for the test case:

2

1 2 3 2

2 1 2 2

1

1 1

0

0 0

The figure is in the form of the alphabet “T”.

Happy coding 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

1. Horizontal segments (any) that lie between (y1+1,y2-1)
2. Horizontal segments (don’t begin or end at x) at y1 and y2.

Thanks, fixed!

//