Problem Description

In the distant “Kingdom of Coordinates”, there are $n$ altars scattered across the land. These altars are the medium through which the kingdom communicates with the gods. Each altar has its own name and position, and their positions are neatly recorded on a 2D plane, never repeating, in order as $(x_1 , y_1 ), (x_2 , y_2 ), \dots , (x_n , y_n )$.

Every hundred years, during the “Energy Awakening Festival”, the king must gather priests from across the country to carry out a solemn and sacred line-linking ceremony on the land. Legend says that when certain altars are connected by sacred beams of light, energy will flow between them, awakening the sleeping giant dragon and the spirits of the earth to protect the whole kingdom. However, the ceremony cannot be done freely. The priests must follow these ancient rules:

1. Exactly $k$ line segments must be chosen in the ceremony, where $k$ is between $1$ and $18$.
2. Each line segment must connect two different altars.
3. Any altar can take part in at most one line segment in the whole ceremony. That is, all endpoints of the chosen segments must be pairwise distinct.
4. No two line segments may cross or overlap on the plane, otherwise they will interfere with each other.

Energy flow is not free. A line segment between two altars consumes the priests’ mana, and the amount consumed is proportional to their distance. The distance between altar $i$ and altar $j$, located at $(x_i , y_i )$ and $(x_j , y_j )$, is defined as the Euclidean distance:

$$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$

Therefore, if the chosen segments are too long, it will be a heavy burden for the priests. If their mana is not enough, the ceremony will fail. On the other hand, if we can find suitable altars so that the total segment length is minimized, the ceremony can be completed with the least mana consumption and release the greatest energy.

As the kingdom’s royal problem solver, you carry a heavy responsibility. The king gives you the coordinates of the altars and asks you to compute the minimum total mana consumption. For convenience, we use the total length of the chosen segments to represent the priests’ total mana consumption. Your answer will directly decide whether the ceremony can be completed smoothly, and may even affect the survival of the kingdom.

Input Format

$$\begin{aligned} &n \; k \\ &x_1 \; y_1 \\ &x_2 \; y_2 \\ &\vdots \\ &x_n \; y_n \end{aligned}$$

• $n$ is the number of altars.
• $k$ is the number of segments to be chosen.
• $x_i,y_i$ means the coordinate of the $i$-th altar is $(x_i,y_i)$.

Output Format

$$a$$

• $a$ is the minimum total mana consumption. An absolute or relative error within $10^{-6}$ is accepted. That is, if the correct answer is $b$, then your answer will be considered correct as long as it satisfies$$\frac{\lvert a - b \rvert}{\max(\lvert a \rvert, \lvert b \rvert, 1)} \leq 10^{-6}$$

3 1
0 0
0 3
9 9

3.0000000000

4 2
0 0
1 0
5 5
5 6

2.0000000000

Hint

Constraints

• $1 \leq k \leq 18$.
• $2k \leq n \leq 10^5$.
• $0 \leq x_i, y_i \leq 10^9$.
• All altar coordinates are distinct.
• All input numbers are integers.

Scoring

This problem has seven subtasks, with additional constraints as follows.
Each subtask may contain one or more testdata files, and you will get the score for that subtask only if you pass all testdata files in it.

Subtask	Score	Additional Input Constraints
1	13	$k = 1$.
2	8	$n \leq 20$，$k \leq 10$.
3	11	$n \leq 3000$，$k \leq 2$.
4	15	$k \leq 2$.
5	26	$n \leq 3000$，$k \leq 15$.
6	17	$k \leq 15$.
7	10	No additional constraints.

Translated by ChatGPT 5