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

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

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

1. 两颗卫星距离过近会产生干扰，降低导航精度；
2. 星座必须保持连通性（通信半径为 ，任意两颗卫星都能通过直接或间接通信到达）；
3. 在综合考虑以上因素后，使总导航精度最大化。

导航精度计算规则

设选定的导航空座包含卫星集合 ，每颗卫星 位于坐标 ，信号强度为 。

• 基础精度：每颗卫星贡献的基础精度为其信号强度 。
• 几何加成：考虑星座的几何分布，计算所有卫星对之间的几何加成：

其中 是卫星 和 之间的欧几里得距离。

连通性约束：

• 如果两颗卫星距离 ，则它们可以直接通信。
• 整个星座必须保持连通（任意两颗卫星都能通过直接或间接通信到达）。

干扰惩罚：

如果两颗卫星距离过近（），会产生信号干扰，精度减少：

其中 是指示函数，当条件满足时为 ，否则为 ；对每一对不同的卫星（）各计算一次干扰惩罚。

总导航精度计算公式：

给定 颗候选卫星的坐标和信号强度，以及通信半径 和干扰阈值 ，从中选择若干颗卫星组成导航空座，使得：

1. 星座保持连通性（通信半径为 ）；
2. 总导航精度最大化；
3. 星座中至少包含 颗卫星。

第一行包含四个整数 、、、，分别表示候选卫星数量、最少卫星数量、通信半径和干扰阈值。

接下来 行，每行包含三个整数 、、，表示第 颗卫星的坐标和信号强度。

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

样例输入 1

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

样例输出 1

39

样例输入 2

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

样例输出 2

139

【样例说明 1】

最优解：选择卫星 （编号从 开始），即坐标为 、、 的三颗卫星。

连通性验证：

• ✓
• ✓
• ✓

所有卫星对都能直接通信，星座连通。

精度计算：

1. 基础精度：。

2. 几何加成：

   • 卫星 1-2：；
   • 卫星 1-3：；
   • 卫星 2-3：。

   总几何加成：。

3. 干扰惩罚：所有距离都 ，无干扰惩罚。

总精度：，向下取整为 39。

【样例说明 2】

最优解：选择卫星 （编号从 开始），即坐标为 、、、 的四颗卫星。

连通性验证：

• ✓
• ✓
• ✓
• ✓
• ✓
• ✓

所有选中卫星对都能直接通信，星座连通。

精度计算：

1. 基础精度：

2. 几何加成：

   • 卫星 1-2：；
   • 卫星 1-3：；
   • 卫星 1-5：；
   • 卫星 2-3：；
   • 卫星 2-5：；
   • 卫星 3-5：。

总几何加成：。

3. 干扰惩罚：

• 卫星 1-2 距离 ，产生干扰：；
• 卫星 2-3 距离 ，产生干扰：；
• 其他卫星对距离都 ，无干扰。

总干扰惩罚：

总精度：，向下取整为 139。

【评测用例规模与约定】

对于 的数据：，；

对于 的数据：，；

对于所有评测用例：

• ，，，；
• 坐标范围：；
• 信号强度：；
• 保证存在至少 颗卫星、且满足连通性约束的解。