How to solve this problem in O(log(n)*n)?

Question

Algorithms

Good afternoon. Faced difficulties in solving the problem in O(log(n)*n) time. The essence of the problem: there is a coordinate plane on which, along the X axis, circles with certain radii are located. An array A is given in which the index - denotes the center of the circle on the X axis, and the value - the radius of this circle. We need to find the number of intersections. Here is a link to the task https://codility.com/programmers/task/number_of_di... I'm not asking for a complete solution, push where to dig

Answer 1

Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Judging by the description, this is not O (n), not greedy and not single pass. Possible dynamic programming + sorting.

Answer 2

This problem can be solved by the scanning line method. Add 2 points for each circle on the circle: the point of the first intersection with the line and the point of the second intersection with the line. A point is actually a structure that knows its coordinate, which circle it belongs to, and whether it is a point with a smaller or larger x-coordinate for this line)
For N log N, sort the circles by X values.
Next, we look through all the circles. At each step, we need to decide how to update the intersection count. Next, draw the options on a piece of paper and find a solution :)

Answer 3

Let's create an array for 2N events. Event - this type ("beginning" / "end"), lap number and coordinate. Each circle creates two events: start at i−R and end at i+R.
The array is sorted by X, with such specification if X are equal.
• If tangency is considered an intersection, start < end (ie for point X there are beginnings, then ends). In such a situation, we do not care about the numbers of circles.
• If not, first lap numbers (aka x-coordinates of centers) in ascending order, then start < end.
We start the counter of circles. Let's go through the array.
• If we see the beginning - to the result + counter, to the counter +1.
• If we see the end - to the counter -1.
In our example:
Counter 0, result 0
Start #1 at x=−4: result 0, counter 1
Start #0 at x=−1: result 1, counter 2
Start #2 at x=0: result 3, counter 3
Start #4 at x=0: result 6, counter 4
End #0 at x=1: counter 3
Start #3 at x=2: result 9, counter 4
Then two ends at x=4, counter down to 2
Start #5 at x=5: result 11, counter 3
End #5 at x=5: counter 2
AND two more ends reset the counter to 0.
UPD. Clarified for the case if the touch is not an intersection.