P16272 [蓝桥杯 2026 省 Java B 组] 星座导航校准器

深空探测器在执行任务时需要依靠星座导航系统进行精确定位。该系统由若干颗导航卫星组成，每颗卫星都有固定的轨道位置和信号强度。 为了确保导航精度，需要选择一组卫星构成“导航空座”，使得： 1. 两颗卫星距离过近会产生干扰，降低导航精度； 2. 星座必须保持连通性（通信半径为 $R$，任意两颗卫星都能通过直接或间接通信到达）； 3. 在综合考虑以上因素后，使总导航精度最大化。 #### 导航精度计算规则 设选定的导航空座包含卫星集合 $S = \{s_1, s_2, \dots, s_k\}$，每颗卫星 $s_i$ 位于坐标 $(x_i, y_i)$，信号强度为 $p_i$。 - **基础精度**：每颗卫星贡献的基础精度为其信号强度 $p_i$。 - **几何加成**：考虑星座的几何分布，计算所有卫星对之间的几何加成： $$ \begin{aligned} \text{GeometricBonus} = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} \frac{p_i \times p_j}{\sqrt{d_{ij}^2 + 1}} \end{aligned} $$ 其中 $d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ 是卫星 $s_i$ 和 $s_j$ 之间的欧几里得距离。 #### 连通性约束： - 如果两颗卫星距离 $d_{ij} \leq R$，则它们可以直接通信。 - 整个星座必须保持连通（任意两颗卫星都能通过直接或间接通信到达）。 #### 干扰惩罚： 如果两颗卫星距离过近（$d_{ij} < T$），会产生信号干扰，精度减少： $$ \begin{aligned} \text{InterferencePenalty} = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} \mathbf{1}_{d_{ij} < T} \cdot (T - d_{ij}) \times \min(p_i, p_j) \end{aligned} $$ 其中 $\mathbf{1}_{d_{ij} < T}$ 是指示函数，当条件满足时为 $1$，否则为 $0$；对每一对不同的卫星（$i < j$）各计算一次干扰惩罚。 #### 总导航精度计算公式： $$ \begin{aligned} \text{TotalPrecision} = \sum_{i=1}^{k} p_i + \text{GeometricBonus} - \text{InterferencePenalty} \end{aligned} $$ 给定 $N$ 颗候选卫星的坐标和信号强度，以及通信半径 $R$ 和干扰阈值 $T$，从中选择若干颗卫星组成导航空座，使得： 1. 星座保持连通性（通信半径为 $R$）； 2. 总导航精度最大化； 3. 星座中至少包含 $K$ 颗卫星。

第一行包含四个整数 $N$、$K$、$R$、$T$，分别表示候选卫星数量、最少卫星数量、通信半径和干扰阈值。 接下来 $N$ 行，每行包含三个整数 $x_i$、$y_i$、$p_i$，表示第 $i$ 颗卫星的坐标和信号强度。

输出一行，包含一个整数，表示能够达到的最大导航精度（向下取整）。

### 【样例说明 1】 最优解：选择卫星 $\{1, 2, 3\}$（编号从 $1$ 开始），即坐标为 $(0, 0)$、$(5, 0)$、$(0, 5)$ 的三颗卫星。 #### 连通性验证： - $d_{12} = \sqrt{(0 - 5)^2 + (0 - 0)^2} = 5 \leq R = 10$ ✓ - $d_{13} = \sqrt{(0 - 0)^2 + (0 - 5)^2} = 5 \leq R = 10$ ✓ - $d_{23} = \sqrt{(5 - 0)^2 + (0 - 5)^2} = \sqrt{50} \approx 7.07 \leq R = 10$ ✓ 所有卫星对都能直接通信，星座连通。 #### 精度计算： 1. **基础精度**：$5 + 8 + 6 = 19$。 2. **几何加成**： - 卫星 1-2：$\frac{5 \times 8}{\sqrt{5^2 + 1}} = \frac{40}{\sqrt{26}} \approx 7.84$； - 卫星 1-3：$\frac{5 \times 6}{\sqrt{5^2 + 1}} = \frac{30}{\sqrt{26}} \approx 5.88$； - 卫星 2-3：$\frac{8 \times 6}{\sqrt{50 + 1}} = \frac{48}{\sqrt{51}} \approx 6.72$。 总几何加成：$7.84 + 5.88 + 6.72 = 20.44$。 3. **干扰惩罚**：所有距离都 $\geq 5 > T = 3$，无干扰惩罚。 总精度：$19 + 20.44 - 0 = 39.44$，向下取整为 **39**。 ### 【样例说明 2】 最优解：选择卫星 $\{1, 2, 3, 5\}$（编号从 $1$ 开始），即坐标为 $(0, 0)$、$(2, 0)$、$(4, 0)$、$(1, 4)$ 的四颗卫星。 #### 连通性验证： - $d_{12} = 2 \leq R = 5$ ✓ - $d_{13} = 4 \leq R = 5$ ✓ - $d_{15} = \sqrt{1^2 + 4^2} = \sqrt{17} \approx 4.12 \leq R = 5$ ✓ - $d_{23} = 2 \leq R = 5$ ✓ - $d_{25} = \sqrt{1^2 + 4^2} = \sqrt{17} \approx 4.12 \leq R = 5$ ✓ - $d_{35} = \sqrt{3^2 + 4^2} = 5 \leq R = 5$ ✓ 所有选中卫星对都能直接通信，星座连通。 #### 精度计算： 1. **基础精度**：$10 + 8 + 6 + 9 = 33$ 2. **几何加成**： - 卫星 1-2：$\frac{10 \times 8}{\sqrt{2^2 + 1}} = \frac{80}{\sqrt{5}} \approx 35.78$； - 卫星 1-3：$\frac{10 \times 6}{\sqrt{4^2 + 1}} = \frac{60}{\sqrt{17}} \approx 14.55$； - 卫星 1-5：$\frac{10 \times 9}{\sqrt{17 + 1}} = \frac{90}{\sqrt{18}} \approx 21.21$； - 卫星 2-3：$\frac{8 \times 6}{\sqrt{2^2 + 1}} = \frac{48}{\sqrt{5}} \approx 21.47$； - 卫星 2-5：$\frac{8 \times 9}{\sqrt{17 + 1}} = \frac{72}{\sqrt{18}} \approx 16.97$； - 卫星 3-5：$\frac{6 \times 9}{\sqrt{5^2 + 1}} = \frac{54}{\sqrt{26}} \approx 10.59$。 总几何加成：$35.78 + 14.55 + 21.21 + 21.47 + 16.97 + 10.59 = 120.57$。 #### 3. 干扰惩罚： - 卫星 1-2 距离 $2 < T=3$，产生干扰：$(3 - 2) \times \min(10, 8) = 1 \times 8 = 8$； - 卫星 2-3 距离 $2 < T=3$，产生干扰：$(3 - 2) \times \min(8, 6) = 1 \times 6 = 6$； - 其他卫星对距离都 $\geq 3$，无干扰。 总干扰惩罚：$8 + 6 = 14$ 总精度：$33 + 120.57 - 14 = 139.57$，向下取整为 **139**。 ### 【评测用例规模与约定】 对于 $30\%$ 的数据：$N \leq 8$，$K \leq 3$； 对于 $60\%$ 的数据：$N \leq 12$，$K \leq 5$； 对于所有评测用例： - $N \leq 15$，$K \leq 8$，$R \leq 20$，$T \leq 10$； - 坐标范围：$0 \leq x_i, y_i \leq 100$； - 信号强度：$1 \leq p_i \leq 20$； - 保证存在至少 $K$ 颗卫星、且满足连通性约束的解。