Finding the number of intersections of $n$ line segments with endpoints on two parallel lines
Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p_1, \dots, p_n$ in order of increasing $x$ coordinate to obtain an ordered list $p[1],p[2], \dots, p[n]$. We now relabel the points $q_1, \dots, q_n$ with respect to this new ordering of the $p$'s such that $p[i]$ and $q[i]$ are endpoints of a line segment, for all $1 \leq i \leq n$. Altogether, these steps take $O(n \log n)$ time.

Now, we want to count the number of inversions in $q[1], \dots, q[n]$; an inversion is a situation where $i &lt; j$ and $q[i] &gt; q[j]$ (we compare the points by their $x$ coordinates). This is because $i &lt; j$ implies $p[i] &lt; p[j]$ by construction, and $p[i] &lt; p[j]$ and $q[i] &gt; q[j]$ if and only if the line segments $(p[i], q[i])$ and $(p[j], q[j])$ intersect. Hence, the number of line segment intersections is precisely the number of inversions in $q[1], \dots, q[n]$.

There is a well known divide and conquer approach for counting these inversions. Can you take it from here?