NOI 竞赛模拟题：引爆最多炸弹

题目描述

在坐标系中有 $n$ 个炸弹。每个炸弹的位置由其坐标 $(x, y)$ 和爆炸半径 $r$ 决定。

如果一个炸弹爆炸，它会引爆其爆炸范围内的所有炸弹。一个炸弹 $A$ 能引爆炸弹 $B$，当且仅当炸弹 $B$ 到炸弹 $A$ 的欧几里得距离小于或等于炸弹 $A$ 的爆炸半径 $r_A$。

注意：引爆关系是单向的。例如，炸弹 $A$ 可能在炸弹 $B$ 的引爆范围内，但炸弹 $B$ 不一定在炸弹 $A$ 的引爆范围内。

现在你可以选择引爆恰好一个初始炸弹。请计算并输出引爆后能产生的最大炸弹爆炸总数（包括初始引爆的那个炸弹）。

---

输入格式

第一行包含一个整数 $n$，表示炸弹的数量。 接下来 $n$ 行，每行包含三个整数 $x_i, y_i, r_i$，分别表示第 $i$ 个炸弹的横坐标、纵坐标和爆炸半径。

输出格式

输出一个整数，表示选择一个炸弹引爆后，最多能引爆的炸弹数量。

---

输入输出样例

样例 1

输入：

2
1 2 3
2 3 1

输出：

2

解释：炸弹 0 位于 (1, 2) 半径为 3；炸弹 1 位于 (2, 3) 半径为 1。炸弹 1 在炸弹 0 的范围内，引爆 0 会引爆 1。

样例 2

输入：

2
2 1 3
6 1 4

输出：

2

解释：引爆炸弹 0 只能引爆自己；引爆炸弹 1 可以引爆 0。最大值为 2。

样例 3

输入：

5
1 1 5
10 10 5
2 1 10
3 3 0
5 12 12

输出：

5

---

数据范围与提示

• $1 \le n \le 2100$
• $1 \le x_i, y_i, r_i \le 10^5$
• 所有坐标和半径均为整数。

---

1. 预备知识点

• 计算几何基础：两点间距离公式 $d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$。
• 有向图建模：若 A 能引爆 B，则建立一条从 A 到 B 的有向边。
• 图的遍历 (DFS/BFS)：从每个点出发求可达节点的数量。
• 溢出处理：在计算距离平方时需注意 long long 类型的应用。

---

2. 启发式思路引导（草稿纸上的思考过程）

第一步：抽象为图论模型

• 每个炸弹是一个节点。
• 核心判断：对于任意两个炸弹 $i$ 和 $j$，计算距离 $D_{ij}$。如果 $D_{ij} \le r_i$，则添加一条有向边 $i \to j$。
• 重点：引爆关系不具有对称性。必须按有向图处理。

第二步：几何计算优化

• 距离公式涉及根号，可能产生精度误差。
• 优化：比较 $D_{ij}^2 \le r_i^2$。即 $(x_i - x_j)^2 + (y_i - y_j)^2 \le r_i^2$。
• 数值预估：坐标差最大为 $2 \cdot 10^5$，其平方为 $4 \cdot 10^{10}$，这超过了 int 的范围（约 $2 \cdot 10^9$），必须使用 long long 存储计算结果。

第三步：寻找最大引爆数

• 题目要求：从一个炸弹开始。
• 目标：求出从节点 $i$ 出发，能够到达的不同节点总数。
• 对每个节点 $i \in [0, n-1]$，分别跑一次 DFS 或 BFS。

第四步：复杂度分析与思考

• 建图：$O(n^2)$。
• 遍历：共 $n$ 次遍历，每次遍历最坏 $O(n + e)$，总复杂度 $O(n(n+e))$。
• 由于 $e \le n^2$，总复杂度上限 $O(n^3)$。
• 对于 $n=2100$，$n^3$ 约为 $9 \cdot 10^9$，直接运行可能超时。
• 时间优化建议：
  1. 使用邻接表而非邻接矩阵减少遍历常数。
  2. 使用 bitset 优化有向图的可达性（传递闭包），复杂度降为 $O(n^3/64)$。
  3. 在 DFS 过程中，若发现已经引爆了所有炸弹（$count == n$），可直接提前终止并输出结果。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 读入 n 及炸弹信息数据"] --> B["构建有向图: 遍历所有点对 i, j"]
    B --> C{"计算距离平方与半径平方关系"}
    C -- "距离平方小于等于半径平方" --> D["添加有向边 i 箭头 j"]
    C -- "否则" --> B
    D --> B
    B -- "建图完成" --> E["初始化 max_count 等于 0"]
    E --> F{"遍历起点节点 k 从 0 到 n-1"}
    F -- "遍历结束" --> G["输出 max_count"]
    F -- "选择起点 k" --> H["初始化 visited 数组和当前计数 cur_count"]
    H --> I["从 k 开始执行 DFS 搜索"]
    I --> J{"发现未访问的邻居 m?"}
    J -- "是" --> K["标记 m 为已访问, cur_count 加 1"]
    K --> I
    J -- "否 (当前分支结束)" --> L["更新 max_count 等于 max{max_count, cur_count}"]
    L --> F

---

4. 读题关键词与坑点总结

1. “单向引爆”：绝对不能建成无向图，否则会导致结果偏大。
2. “欧几里得距离”：必须使用两点距离公式。
3. “恰好一个初始炸弹”：意味着我们只能从一个节点开始扩散。
4. 数值溢出：计算 $(x_i - x_j)^2$ 时，两个 $10^5$ 级别的数相乘会爆 int。在 C++ 中务必写成 1LL * (xi - xj) * (xi - xj)。
5. 半径为 0：注意有的炸弹半径可能是 0，它只能引爆自己（如果坐标重合则可能引爆重合的点，需严格遵守公式）。

5. NOI 竞赛风格建议

• 使用 std::vector<int> adj[2105] 构建邻接表。
• 遍历前使用 std::memset(vis, 0, sizeof(vis)) 清空访问标记。
• 考虑到 $N=2100$ 且时限通常为 1.0s，DFS 的递归深度不会太深，但如果追求稳定，可以使用手写栈或 BFS。
• 如果数据分布极其稠密，$O(N^3)$ 可能通过，但在 NOI 赛场上应考虑是否有更优的强连通分量 (SCC) 缩点方案（虽然缩点主要用于处理环，对本题可达性统计有一定辅助作用，但直接 BFS 往往最稳）。