由多个圆组成的相交区域数

Question

我们有四个参数来绘制一些圆圈：

圆心（x_1和x_2）都位于x轴上
最大半径(k_1 and k_2) 这就是我们如何使用 info:the 第一组圆心位于 x_1，我们从这里绘制 k_1 个不同半径的圆，从 1 到 k_1：(1<= r_1 <= k_1) 所以第一个圆的半径为 1 并以 x_1 为中心，第二个圆的半径为 2 ...同样的条件适用于第二组 circles.In 最后有有些圆圈可能与每个 other.What 相交，也可能不相交我想要的是 end.I 中的区域总数如果我理解两个区域之间的区别，那么问题主要是 solved.To 这里有一些例子（注意所有参数都在：[1,10^5] 范围内）：

for:x_1 = 1,k_1 = 1,x_2 = 0,k_2 = 1 => n = 3
for: x_1 = 0,k_1 = 1,x_2 = 2,k_2 = 1 => n = 2
for:x_1 = 3,k_1 = 3,x_2 = 7,k_2 = 4 => n =16

Answer 1

我想出了以下解决方案。

如您所写，我们有两组圆圈。一组的中心是 x_1，另一组的中心是 x_2 让我们将这些集合表示为 L 和 R，其中

L = 圆心为 x_1 和 R = 圆心为 x_2 和 x_1 <= x_2.

的一组圆

现算法步骤：

首先检查L和R（x_1和x_2）的中心是否相等。如果相等，则这两个集合是同心的。所以答案是k_1和k_2中的最大值。
我们必须确保x_1 <= x_2。如果x_1 > x_2，则交换(x_1,x_2).
在这个算法中，首先我们将计算集合L的每个圆中的区域数。然后我们将计算集合 R 中那些在 x_1 + k_1 之外的区域的计数。所以为了保持良好状态，我们需要交换 k_1 和 k_2，当且仅当 k_1 < k_2 满足。
现在 x_1 <= x_2 为真，我们将计算集合 L 中每个圆圈内的所有区域。然后遍历从 x_1 + 1 到 x_1 + k_1 的所有位置并执行以下操作并尝试从图中捕获不同情况下区域计数的计算：

特例：

我们还要检查另一件事。添加集合 R 中那些在 x_1 + k_1.
之外的区域的计数
- if x_1 + k_1 <= x_2 + k_2 那么 dif = (x_2 + k_2) - (x_1 + k_1) 和 result = result + min(k_2, dif)

这是我的 c++ 实现：

#include <iostream>
using namespace std;

int intersection_count(int x_1, int k_1, int x_2, int k_2) {
    if (x_1 == x_2)
        return max(k_1, k_2);

    if (x_1 > x_2) {
        swap(x_1, x_2);
    }
    if (k_1 < k_2) {
        swap(k_1, k_2);
    }

    int result = 0;
    for (int i = 1; i <= k_1; i++) {
        int pos = x_1 + i;
        int rev_pos = x_1 - i;
        if (pos <= x_2 - k_2) {
            result++;
        }
        else if (pos <= x_2) {
            int dif = pos - (x_2 - k_2);

            // check if the ith circle is cmpletely inside range [x_2 - k_2, x_2 + k_2]
            dif -= (rev_pos < x_2 - k_2) ? 0 : (rev_pos - (x_2 - k_2) + 1);

            result += 2*dif;
        }
        else if (pos <= x_2 + k_2) {
            int dif = (x_2 + k_2) - pos + 1;

            // check if the ith circle is cmpletely inside range [x_2 - k_2, x_2 + k_2]
            dif -= (rev_pos < x_2 - k_2) ? 0 : (rev_pos - (x_2 - k_2) + 1);

            result += 2*dif;
        }
        else {
            result++;
        }
    }
    if (x_1 + k_1 <= x_2 + k_2) {
        int dif = (x_2 + k_2) - (x_1 + k_1);
        result += min(k_2, dif);
    }

    return result;
}

int main(int argc, char const *argv[])
{
    cout << intersection_count(1, 1, 0, 1) << endl;
    cout << intersection_count(0, 1, 2, 1) << endl;
    cout << intersection_count(3, 3, 7, 4) << endl;
    cout << intersection_count(0, 1, 0, 2) << endl;
    cout << intersection_count(2, 1, 3, 2) << endl;
    cout << intersection_count(2, 1, 3, 3) << endl;
    cout << intersection_count(3, 4, 5, 3) << endl;
    cout << intersection_count(0, 7, 2, 7) << endl;

    return 0;
}

由多个圆组成的相交区域数

Number of intersection regions made by multiple circles

algorithm

intersection