几何算法实战：力扣LCP42"玩具套圈"问题的解法详解与优化思路

一、问题描述

给定一组玩具的坐标toys和一组圆环的坐标及半径circles，要求计算有多少个玩具能被至少一个圆环套住。每个圆环由(x,y,r)表示，其中(x,y)是圆心坐标，r是半径。

示例：

输入：toys = [[3,3],[1,2]], circles = [[4,3,1],[3,3,1],[1,2,2]]

输出：2

解释：两个玩具都能被至少一个圆环套住

二、解题思路

采用"暴力枚举+几何判断"策略：

1. 遍历每个玩具

2. 对于每个玩具，检查是否存在至少一个圆环能套住它

3. 判断条件是玩具到圆心的距离 ≤ 圆环半径

三、算法详解

#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;
    }
};

四、算法详解

1. 几何判断原理

• 玩具被圆环套住的条件：玩具中心到圆心的距离 + 玩具半径 ≤ 圆环半径

• 使用欧几里得距离公式：√((x2-x1)² + (y2-y1)²)

2. 优化思路

1. ‌空间分区‌：将圆环按空间划分，减少需要检查的圆环数量

2. ‌排序预处理‌：按圆环半径排序，优先检查大圆环

3. ‌距离平方比较‌：避免开平方运算，比较距离平方

3. 边界条件处理

• 玩具半径大于圆环半径的情况

• 多个圆环重叠的情况

• 玩具正好在圆环边缘的情况

• 空输入的处理

五、关键点解析

1. 几何条件理解

• 玩具完全在圆环内 ≠ 玩具中心在圆环内

• 需要考虑玩具自身的半径(tr)

• 实际判断的是两个圆的包含关系

2. 浮点数处理

• 使用sqrt和pow会引入浮点运算

• 实际比赛中可以比较距离平方避免浮点误差

• 工业场景需要考虑数值稳定性

3. 复杂度分析

• 时间复杂度：O(n*m) 最坏情况下需要检查所有组合

• 空间复杂度：O(1) 只使用了常数额外空间

六、常见错误分析

1. ‌忽略玩具半径‌：只判断中心距离不考虑玩具大小

2. ‌浮点精度问题‌：直接比较浮点数导致误差

3. ‌边界条件遗漏‌：没有处理玩具与圆环相切的情况

4. ‌过早优化‌：在不必要的情况下引入复杂数据结构