题目描述

深空探测器在执行任务时需要依靠星座导航系统进行精确定位。该系统由若干颗导航卫星组成，每颗卫星都有固定的轨道位置和信号强度。

为了确保导航精度，需要选择一组卫星构成“导航空座”，使得：

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$ 颗卫星的坐标和信号强度。

输出格式

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

3 2 10 3
0 0 5
5 0 8
0 5 6

39

解释 #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。

5 3 5 3
0 0 10
2 0 8
4 0 6
10 0 12
1 4 9

139

解释 #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$ 颗卫星、且满足连通性约束的解。