找到相交圆的数量

Question

我遇到了一个面试问题,我无法解决:

给定N个整数的阵列A,我们在2D平面中绘制N个盘,使得第I ^个盘以(0,I)为中心并且具有半径A [I].我们说如果J≠K并且^第 J和^第 K ^个盘具有至少一个公共点,则第J ^个盘和^第 K ^个盘相交.写一个函数:int solution(const vector&A); 如上所述,给定描述N个盘的阵列A,返回交叉盘对的数量.例如,给定N = 6并且:

A[0] = 1  A[1] = 5  A[2] = 2 
A[3] = 1  A[4] = 4  A[5] = 0  

相交光盘出现在十一对元素中:

0 and 1,
0 and 2,
0 and 4,
1 and 2,
1 and 3,
1 and 4,
1 and 5,
2 and 3,
2 and 4,
3 and 4,
4 and 5.

所以函数应该返回11.

到目前为止,您可以找到每两个圆之间的交点,通过使用圆方程计算交点甚至更简单,如果两个中心之间的距离大于两个半径之和,它们相交.该解决方案需要O(N ²).

那么约束是受访者应该提出具有最差时间复杂度O(N.logN)的解决方案并且需要空间O(N).作为提示给出:可以编辑数组的元素.

Whenevr logN说,它弹出一个树或递归,但我再次无法创建新的数据结构,因为所需的空间是O(N).所以我只能想象在数组上只有一个for循环,每一步都会进行某种递归,并根据需要改变数组值.但到目前为止,我已经来了.任何想法都表示赞赏