Robot

Gần đây, VNG đã cho ra mắt sản phẩm mới mang tên Kiki (The Voice Assistant for Vietnamese) — trợ lý ảo bằng giọng nói tiếng Việt giúp người dùng thực hiện nhiều tác vụ chỉ với câu lệnh "Kiki ơi". Kiki đóng vai trò như một trợ lý thường nhật: đặt báo thức, theo dõi danh sách việc cần làm... Đặc biệt, Kiki hoạt động rất ấn tượng trên Zing MP3 khi hỗ trợ tìm bài hát theo tên, lời nhạc, nghệ sĩ hoặc phát ngẫu nhiên, thêm bài hát vào album yêu thích...

Nhận thấy tiềm năng của Kiki, một công ty X đã ngỏ ý hợp tác với VNG để phát triển các robot đơn giản tích hợp Kiki nhằm hỗ trợ nhân viên xử lý các công việc cơ bản, đóng vai trò như trợ lý nội bộ.

Thấy ý tưởng này khá thú vị, VNG quyết định thử nghiệm tại chính doanh nghiệp của mình. Tuy nhiên vì một số hạn chế, VNG chỉ có thể mua k robot và dùng k robot này để phục vụ cho toàn bộ N bộ phận trong công ty. Để tối ưu thời gian di chuyển, VNG cần chọn ra k bộ phận để đặt robot sao cho tổng khoảng cách (theo khoảng cách Euclid) từ mỗi bộ phận đến robot gần nhất là nhỏ nhất (nhờ đó các robot có thể hỗ trợ được tối đa công việc).

Giả sử mỗi bộ phận và mỗi robot là một điểm trên mặt phẳng tọa độ 2D. Khi đó, khoảng cách Euclid từ một robot tại vị trí $(x, y)$ đến một bộ phận tại vị trí $(a, b)$ được tính theo công thức:

$\sqrt{(x-a)^2 + (y-b)^2}$

Hãy giúp VNG xác định tổng khoảng cách nhỏ nhất nhằm tối ưu chi phí di chuyển trong công ty!

Đầu vào:

• Dòng đầu tiên chứa 2 số nguyên dương N $(2 \leq N \leq 20)$ — số lượng bộ phận tại VNG và k $(1 \leq k< N)$ — số lượng robot mà VNG vừa mua.
• N dòng tiếp theo, mỗi dòng chứa 2 số nguyên $x, y$ $(1 \leq x, y \leq 10^9)$ lần lượt biểu diễn tọa độ của từng bộ phận.

Đầu ra: In ra một dòng duy nhất: tổng khoảng cách nhỏ nhất cần tìm (làm tròn đến 2 chữ số thập phân).

Giải thích: Ví dụ 1: Khi đặt robot tại các bộ phận $3, 4, 5, 6$:

• Bộ phận 1 sẽ đến robot đặt ở bộ phận 5 (do có khoảng cách ngắn nhất). Khoảng cách từ bộ phận 1 đến bộ phận 5 là $\sqrt{(6-7)^2+(6-7)^2}=\sqrt{1+1}=\sqrt{2}$.
• Bộ phận 2 sẽ đến robot đặt ở bộ phận 6. Khoảng cách từ bộ phận 2 đến bộ phận 6 là $\sqrt{(5-4)^2+(3-4)^2}=\sqrt{1+1}=\sqrt{2}$.
• Các bộ phận $3, 4, 5, 6$ đã có robot đặt tại đó nên khoảng cách đến robot gần nhất là 0.
• Tổng khoảng cách nhỏ nhất cần tìm là: $\sqrt{2}+\sqrt{2}+0+0+0+0=2\sqrt{2}\approx2.828427$. Làm tròn đến 2 chữ số thập phân, kết quả là $2.83$.

Ví dụ 2: Khi đặt robot tại các bộ phận $2, 4$:

• Bộ phận 1 sẽ đến robot đặt ở bộ phận 4 (do có khoảng cách ngắn nhất). Khoảng cách từ bộ phận 1 đến bộ phận 4 là $\sqrt{(3-5)^2+(1-1)^2}=\sqrt{4+0}=2$.
• Bộ phận 3 sẽ đến robot đặt ở bộ phận 4. Khoảng cách từ bộ phận 3 đến bộ phận 4 là $\sqrt{(5-5)^2+(3-1)^2}=\sqrt{0+4}=2$.
• Các bộ phận $2, 4$ đã có robot đặt tại đó nên khoảng cách đến robot gần nhất là 0.
• Tổng khoảng cách nhỏ nhất cần tìm là: $2+0+2+0=4$. Làm tròn đến 2 chữ số thập phân, kết quả là $4.00$.

Ví dụ 1:

Đầu vào:

6 4
6 6
5 3
10 10
3 10
7 7
4 4

Đầu ra:

2.83

Ví dụ 2:

Đầu vào:

4 2
3 1
2 4
5 3
5 1

Đầu ra:

4.00