Problem Description

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.

Input Format

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 Format

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

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

39

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

139

Hint

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