P16272 [Lanqiao Cup 2026 NOI Qualifier Java B Group] Constellation Navigation Calibrator

When a deep-space probe performs missions, it needs to rely on a constellation navigation system for accurate positioning. The system consists of several navigation satellites. Each satellite has a fixed orbital position and a signal strength. To ensure navigation accuracy, you need to choose a set of satellites to form a “navigation constellation”, such that: 1. If two satellites are too close, they will interfere with each other and reduce navigation accuracy. 2. The constellation must remain connected (with communication radius $R$, any two satellites can reach each other via direct or indirect communication). 3. After considering the above factors, maximize the total navigation accuracy. #### Navigation Accuracy Rules Suppose the selected navigation constellation contains the satellite set $S = \{s_1, s_2, \dots, s_k\}$. Each satellite $s_i$ is located at coordinates $(x_i, y_i)$ and has signal strength $p_i$. - **Base precision**: each satellite contributes base precision equal to its signal strength $p_i$. - **Geometric bonus**: considering the geometric distribution of the constellation, compute the geometric bonus over all satellite pairs: $$ \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} $$ where $d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ is the Euclidean distance between satellites $s_i$ and $s_j$. #### Connectivity constraint: - If the distance between two satellites satisfies $d_{ij} \leq R$, then they can communicate directly. - The entire constellation must stay connected (any two satellites can reach each other through direct or indirect communication). #### Interference penalty: If two satellites are too close ($d_{ij} < T$), signal interference occurs and the precision decreases: $$ \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} $$ where $\mathbf{1}_{d_{ij} < T}$ is the indicator function, which equals $1$ when the condition holds and $0$ otherwise. For each distinct satellite pair ($i < j$), the interference penalty is counted once. #### Total navigation precision formula: $$ \begin{aligned} \text{TotalPrecision} = \sum_{i=1}^{k} p_i + \text{GeometricBonus} - \text{InterferencePenalty} \end{aligned} $$ Given the coordinates and signal strengths of $N$ candidate satellites, as well as the communication radius $R$ and interference threshold $T$, select some satellites to form a navigation constellation such that: 1. The constellation remains connected (communication radius $R$). 2. The total navigation precision is maximized. 3. The constellation contains at least $K$ satellites.

The first line contains four integers $N$, $K$, $R$, $T$, representing the number of candidate satellites, the minimum number of satellites, the communication radius, and the interference threshold. The next $N$ lines each contain three integers $x_i$, $y_i$, $p_i$, representing the coordinates and signal strength of the $i$-th satellite.

Output one line containing one integer, representing the maximum navigation precision that can be achieved (rounded down).

### Sample Explanation 1 Optimal solution: choose satellites $\{1, 2, 3\}$ (indices start from $1$), i.e. the three satellites at $(0, 0)$, $(5, 0)$, and $(0, 5)$. #### Connectivity check: - $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$ ✓ All satellite pairs can communicate directly, so the constellation is connected. #### Precision calculation: 1. **Base precision**: $5 + 8 + 6 = 19$. 2. **Geometric bonus**: - Satellites 1-2: $\frac{5 \times 8}{\sqrt{5^2 + 1}} = \frac{40}{\sqrt{26}} \approx 7.84$. - Satellites 1-3: $\frac{5 \times 6}{\sqrt{5^2 + 1}} = \frac{30}{\sqrt{26}} \approx 5.88$. - Satellites 2-3: $\frac{8 \times 6}{\sqrt{50 + 1}} = \frac{48}{\sqrt{51}} \approx 6.72$. Total geometric bonus: $7.84 + 5.88 + 6.72 = 20.44$. 3. **Interference penalty**: all distances are $\geq 5 > T = 3$, so there is no interference penalty. Total precision: $19 + 20.44 - 0 = 39.44$, rounded down to **39**. ### Sample Explanation 2 Optimal solution: choose satellites $\{1, 2, 3, 5\}$ (indices start from $1$), i.e. the four satellites at $(0, 0)$, $(2, 0)$, $(4, 0)$, and $(1, 4)$. #### Connectivity check: - $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$ ✓ All selected satellite pairs can communicate directly, so the constellation is connected. #### Precision calculation: 1. **Base precision**: $10 + 8 + 6 + 9 = 33$. 2. **Geometric bonus**: - Satellites 1-2: $\frac{10 \times 8}{\sqrt{2^2 + 1}} = \frac{80}{\sqrt{5}} \approx 35.78$. - Satellites 1-3: $\frac{10 \times 6}{\sqrt{4^2 + 1}} = \frac{60}{\sqrt{17}} \approx 14.55$. - Satellites 1-5: $\frac{10 \times 9}{\sqrt{17 + 1}} = \frac{90}{\sqrt{18}} \approx 21.21$. - Satellites 2-3: $\frac{8 \times 6}{\sqrt{2^2 + 1}} = \frac{48}{\sqrt{5}} \approx 21.47$. - Satellites 2-5: $\frac{8 \times 9}{\sqrt{17 + 1}} = \frac{72}{\sqrt{18}} \approx 16.97$. - Satellites 3-5: $\frac{6 \times 9}{\sqrt{5^2 + 1}} = \frac{54}{\sqrt{26}} \approx 10.59$. Total geometric bonus: $35.78 + 14.55 + 21.21 + 21.47 + 16.97 + 10.59 = 120.57$. #### 3. Interference penalty: - Satellites 1-2 have distance $2 < T = 3$, causing interference: $(3 - 2) \times \min(10, 8) = 1 \times 8 = 8$. - Satellites 2-3 have distance $2 < T = 3$, causing interference: $(3 - 2) \times \min(8, 6) = 1 \times 6 = 6$. - All other satellite pairs have distance $\geq 3$, so there is no interference. Total interference penalty: $8 + 6 = 14$. Total precision: $33 + 120.57 - 14 = 139.57$, rounded down to **139**. ### Constraints and Notes for Test Cases For $30\%$ of the testdata: $N \leq 8$, $K \leq 3$. For $60\%$ of the testdata: $N \leq 12$, $K \leq 5$. For all test cases: - $N \leq 15$, $K \leq 8$, $R \leq 20$, $T \leq 10$. - Coordinate range: $0 \leq x_i, y_i \leq 100$. - Signal strength: $1 \leq p_i \leq 20$. - It is guaranteed that there exists a solution with at least $K$ satellites that satisfies the connectivity constraint. Translated by ChatGPT 5