CF199B-Special-Olympics-圆环问题

题解

题目描述

这个问题是一个几何问题，我们需要找出在两个不同心的环形区域中，最多可以找到多少个完整的圆形轮廓。

每个环形区域由一个中心点和两个半径定义，中心点的坐标为 \((x,y)\)，两个半径分别为 \(r\) 和 \(R\)。

算法思路

这个问题的关键在于理解如何判断两个环形区域之间的关系，以及如何从这些环形区域中找出完整的圆形轮廓。

首先，我们需要计算两个环形区域的中心点之间的距离，这可以通过欧几里得距离公式来实现。

然后，我们需要判断两个环形区域之间的关系。这可以通过比较两个环形区域的半径和它们的中心点之间的距离来实现。具体来说，我们需要检查以下三种情况：

1. 两个环形区域的中心点之间的距离小于或等于两个环形区域的内半径之差。这意味着一个环形区域完全包含在另一个环形区域内，因此我们可以从这个环形区域中找出一个完整的圆形轮廓。

2. 两个环形区域的中心点之间的距离小于或等于一个环形区域的内半径和另一个环形区域的外半径之差。这意味着一个环形区域的内圆和另一个环形区域的外圆相交，因此我们可以从这两个环形区域的交集中找出一个完整的圆形轮廓。

3. 两个环形区域的中心点之间的距离大于或等于两个环形区域的外半径之和。这意味着两个环形区域完全分离，因此我们可以从每个环形区域中分别找出一个完整的圆形轮廓。

最后，我们需要对每个环形区域的内半径和外半径，分别与另一个环形区域的内半径和外半径进行上述的判断，将满足条件的情况累加到结果中。

算法原理

首先，我们定义了一个结构体 Circle 来存储每个环形区域的信息，包括中心点坐标 \((x, y)\) 和两个半径 \(r\) 和 \(R\) 。

然后，我们定义了一个函数 computeDistance 来计算两个点之间的距离，使用的是欧几里得距离公式： \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)。

接着，我们定义了一个函数 isCircle 来判断两个环形区域的位置关系。这个函数接受四个参数：两个环心的距离 \(d\)，和两个环的半径 \(r1\)和 \(r2\)。函数返回一个布尔值，表示两个环是否满足内含、外离或相交的条件。

最后，在 main 函数中，我们读入两个环的信息，计算它们的环心距离，然后对每个环的两个半径，分别与另一个环的两个半径进行位置关系的判断，将满足条件的情况累加到答案中。

代码解析

#include <iostream>
#include <cmath>

struct Circle
{
    long long x, y, innerRadius, outerRadius;
};

double computeDistance(Circle c1, Circle c2)
{
    return std::sqrt((c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y));
}

bool isCircle(double d, long long r, long long r1, long long r2)
{
    return (d <= r1 - r) || (d <= r - r2) || (d >= r + r2);
}

int main()
{
    Circle c1, c2;
    std::cin >> c1.x >> c1.y >> c1.innerRadius >> c1.outerRadius;
    std::cin >> c2.x >> c2.y >> c2.innerRadius >> c2.outerRadius;
    int result = 0;
    double d = computeDistance(c1, c2);
    result += isCircle(d, c1.innerRadius, c2.innerRadius, c2.outerRadius);
    result += isCircle(d, c1.outerRadius, c2.innerRadius, c2.outerRadius);
    result += isCircle(d, c2.innerRadius, c1.innerRadius, c1.outerRadius);
    result += isCircle(d, c2.outerRadius, c1.innerRadius, c1.outerRadius);
    std::cout << result;
    return 0;
}

时间复杂度

由于我们只需要对输入的两个环进行一次计算，所以这个程序的时间复杂度是 \(O(1)\)。