Tại một khu vực ở Bắc Cực có tổng cộng ngôi làng, tọa độ của mỗi ngôi làng được biểu diễn bằng một cặp số nguyên (). Để tăng cường liên lạc, người ta quyết định xây dựng mạng lưới thông tin giữa các ngôi làng. Công cụ liên lạc có thể là máy thu phát vô tuyến hoặc thiết bị vệ tinh.
Tất cả các ngôi làng đều có thể sở hữu một máy thu phát vô tuyến, và tất cả các máy thu phát đều cùng một loại. Tuy nhiên, số lượng thiết bị vệ tinh có hạn, chỉ có thể trang bị cho một số ngôi làng.
Các loại máy thu phát vô tuyến khác nhau có một tham số khác nhau, khoảng cách giữa hai ngôi làng nếu không vượt quá thì có thể dùng loại máy này để liên lạc trực tiếp, càng lớn thì giá càng đắt. Hai ngôi làng sở hữu thiết bị vệ tinh có thể liên lạc trực tiếp bất kể khoảng cách bao xa.
Hiện có thiết bị vệ tinh, hãy viết một chương trình tính toán cách phân bổ thiết bị này sao cho giá trị của các máy thu phát vô tuyến cần dùng là nhỏ nhất, đồng thời đảm bảo mỗi cặp ngôi làng đều có thể liên lạc trực tiếp hoặc gián tiếp với nhau.
Ví dụ, với ba ngôi làng dưới đây:
Trong đó .
Nếu không có thiết bị vệ tinh nào hoặc chỉ có 1 thiết bị ( hoặc ), thì nhỏ nhất thỏa mãn điều kiện là . Vì và , và có thể liên lạc trực tiếp bằng vô tuyến; còn và có thể liên lạc gián tiếp qua trung gian (tin nhắn từ truyền đến , rồi từ truyền đến ).
Nếu có 2 thiết bị vệ tinh (), ta có thể phân bổ cho và , khi đó nhỏ nhất có thể lấy là . Vì và liên lạc trực tiếp bằng vô tuyến; và liên lạc trực tiếp bằng vệ tinh; và liên lạc gián tiếp qua trung gian .
Nếu có 3 thiết bị vệ tinh, thì đôi một đều có thể liên lạc bằng vệ tinh, nhỏ nhất có thể là .
Dữ liệu:
Dòng đầu tiên gồm hai số nguyên cách nhau bởi dấu cách .
Các dòng từ , mỗi dòng gồm hai số nguyên, dòng thứ chứa là tọa độ của ngôi làng thứ .
Kết quả:
Một số thực, biểu thị giá trị nhỏ nhất, kết quả làm tròn đến 2 chữ số thập phân.
