Let there be two sets of $n$ points:
$A=\{p_1, p_2, \dots, p_n\}$ on $y=0$
$B=\{q_1, q_2, \dots, q_n\}$ on $y=1$
Each point $p_i$ is connected to its corresponding point $q_i$ to form a line segment.
Example:
I need to write a divide-and-conquer algorithm which returns the number of intersection points of all $n$ line segments and runs in $O(n logn)$.
I was reading about Sweep Line Algorithm but found out its complexity depends on the number of intersections, which can be ${O}{n\choose 2} \subseteq O(n^2)$ (besides the fact that it isn't a divide-and-conquer algorithm). I believe I should use the fact that each set of points has the same $y$ value, but I'm not sure how. Any suggestions?