假设我们给出了 n 个循环，它们构造了单元格 Ci。 给出了每个圆的中点(x-y 坐标)和半径。 细胞的特征在于其限制该细胞的弧线。
对于每个弧，都会给出以下信息: 1. 所属圆的中点 2.源点和目标点为x-y坐标，圆弧的起点和终点。 3. 圆弧本身的中点也给出了它的 x-y 坐标。
对于 Cell1，我将弧线着色为黄色、蓝色和棕色。另外，我尝试在图片上指出圆弧的中点、目标和来源。
现在，我想计算每个单元格包含的圆圈数，运行时间为 O(n²)。 例如，单元格 C1 仅包含在 1 个圆中，单元格 C11 包含在 2 个圆中，单元格 C5 包含在 3 个圆中。
我的想法是在 O(m) 中计算它，其中 m:= 弧数。 我认为一般来说弧的数量可以超过n²。
任何帮助或想法将不胜感激!提前致谢。
最佳答案
我认为一般来说弧的数量可以超过n²。
你为什么这么认为？
任何一对圆最多相交于两个地方。所以单个圆最多会被分为 2n - 2其他圆的弧。既然有n圈子里最多有 2n<sup>2</sup> - 2n = O(n<sup>2</sup>)弧线。
关于performance - 计算一个单元格包含的圆圈数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27235852/