Consider a set S of 2n line segments in 2D: n horizontal and n vertical. Assume that no two segments have endpoints at the same x-coordinate or y-coordinate. It is easy to determine if two given segments intersect, in constant time, by comparing the coordinates of their 4 endpoints, so dont worry about that detail. Your job is to provide a sub-quadratic-time algorithm (i.e., ?(n 2 ) doesnt cut it) to count how many intersections there are among the segments in S. Note that you do not need to list the intersections, just report how many there are.