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

Question

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

1. 圆心(x_1和x_2)都位于x轴上

2. 最大半径(k_1 和 k_2) 这就是我们使用此信息的方式:第一组圆心位于 x_1 ，我们从这里画出 k_1 个不同半径的圆，从 1 到 k_1:(1<= r_1 <= k_1)所以第一个圆的半径为 1 并以 x_1 为中心，第二个圆的半径为 2 ...同样的条件适用于第二组圆。最后有一些圆可能与也可能不相交彼此。我想要的是最后制作的区域总数。我想如果我理解是什么将两个区域分开，问题就主要解决了。为了清楚这里有一些例子(注意所有参数都在: [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 .

现在算法步骤:

1. 首先检查中心是否为L和 R ( x_1 和 x_2 )是否相等。如果相等，则这两个集合是同心的。所以答案是 k_1 的最大值和 k_2 .

2. 我们必须确保x_1 <= x_2 .如果x_1 > x_2 , 然后交换( x_1 , x_2 )。

3. 在此算法中，首先我们将计算集合 L 的每个圆中的区域数.然后我们将计算集合 R 中区域的数量。那些在x_1 + k_1之外.所以为了保持良好状态，我们需要 交换 k_1和 k_2 , 当且仅当 k_1 < k_2会面。

4. 现在 x_1 <= x_2是真的，我们将计算集合 L 中每个圆圈内的所有区域.然后从 x_1 + 1 遍历所有位置至 x_1 + k_1并按照以下步骤尝试从图中捕获不同情况下区域计数的计算:

特例:

1. 我们还需要检查另一件事。添加集合中的区域计数 R那些在x_1 + k_1之外.

   • 如果 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;
}