【力扣LCR42题解析】套圈游戏：用距离平方优化算法解题

一、题目解读

力扣LCR42题“圆圈游戏”要求计算给定玩具集合中，能被套圈覆盖的玩具数量。每个玩具和套圈均由坐标及半径定义，需判断玩具是否在套圈覆盖范围内。题目核心在于高效计算点与圆的位置关系，并统计符合条件的结果。

二、解题思路

采用“半径预筛选+距离平方判定”策略：

1. 过滤无效玩具：优先排除半径大于套圈半径的玩具（因不可能被覆盖）。

2. 逐点验证覆盖：对剩余玩具，遍历所有套圈计算其与圆心距离平方，利用平方避免开方运算，通过比较距离平方与半径差平方判断是否覆盖。

3. 优化计算逻辑：通过提前终止（找到覆盖即break）减少冗余遍历。

三、解题步骤

1. 初始化计数器：count记录被覆盖玩具数量。

2. 外层循环：遍历玩具列表，解析坐标与半径(tx, ty, tr)。

3. 半径过滤：若tr > r（玩具半径大于套圈半径），跳过当前玩具。

4. 内层循环：遍历套圈列表，计算玩具与套圈圆心距离平方(dx^2 + dy^2)。

5. 覆盖判定：若距离平方小于半径差平方(r - tr)^2，标记覆盖并跳出内层循环。

6. 统计结果：若玩具被覆盖，计数器递增。

7. 返回最终数量。

四、代码与注释

#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) {
        int count = 0; // 初始化覆盖计数
        for (const auto& toy : toys) { // 遍历玩具
            int tx = toy[0], ty = toy[1], tr = toy[2];
            // 玩具半径必须小于等于套圈半径才可能被套住
            if (tr > r) continue;
            
            bool covered = false; // 标记是否被覆盖
            for (const auto& circle : circles) {
                int cx = circle[0], cy = circle[1];
                // 计算两点间距离平方(避免浮点运算)
                long dx = tx - cx, dy = ty - cy;
                long distance_sq = dx * dx + dy * dy;
                long max_distance = r - tr; // 允许最大距离平方
                // 比较距离平方与半径平方差
                if (distance_sq <= max_distance * max_distance) {
                    covered = true;
                    break; // 找到覆盖即终止
                }
            }
            if (covered) count++;
        }
        return count;
    }
};

五、总结

本解法通过半径预筛选降低无效计算，结合距离平方判定避免浮点误差，通过提前终止循环优化时间复杂度。核心在于将几何问题转化为代数比较，兼顾效率与准确性。适用于处理大量坐标与半径的覆盖判定场景。