I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson’s book Algorithms.
I solved (a) by seeing a relationship to the previous problem on computing the number of array inversions. However, I am struggling with problem (b) as I cannot see how to reduce the circle point arrangement to an arrangement of points and lines that would be an input to the problem posed in (a). Assuming I have something for (b), I also cannot see how one might resolve (c).
For part (b), clearly every point $ p = (x, y)$ satisfies $ x^2 + y^2 = 1$ but I do not see how I might be able to use this fact to do the reduction. The runtime I am shooting for of $ O(n \log^2 n)$ also seems to tell me the reduction is going to cost something non-trivial to do.
Can anyone have some further hints/insights that might help with part (b) and potentially even part (c)?