This is from Jeffrey Erickson's Algorithms notes
Problem 14 asks for an algorithm to count "inversions," in an array(the number of pairs of items out of sorted order) in $\Theta(n\log(n))$ time. I will assume that this is solved in the question that follows.
Problem 15(a). asks to count intersections of lines from $y=1$ to $y=0$. My thought was to sort the $p_i$ by distance from the origin then assign new indices by index in the sorted array(taking $\Theta(n\log(n)$) time using merge sort). Then put the $q_i$ in an array sorted by index. The number of inversions in this array can be counted in $\Theta(n\log(n))$ using (14). and it will be the number of intersections.
Is this right?
15(b) and 15(c) ask to count the number of intersections of secant lines on a circle in $n\log^2(n)$ time and $n\log(n)$ time respectively. Here is where I am completely stuck. I don't see how to apply a solution to (a). to (b). Do you stretch the circle out somehow? Or divide the points in two?
Any help is appreciated.