Trạm Trung Chuyển Tối Ưu
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ kho hàng nằm tại các tọa độ $(x_i, y_i)$ trên mặt phẳng $Oxy$. Công ty muốn xây dựng một trạm trung chuyển duy nhất tại một điểm $P(x, y)$ bất kỳ (tọa độ thực) sao cho tổng khoảng cách Euclid từ $P$ đến tất cả $N$ kho hàng là nhỏ nhất.
Hãy tìm giá trị nhỏ nhất của tổng khoảng cách đó.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 500$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($|x_i|, |y_i| \le 10^4$).
Kết quả
- In ra một số thực duy nhất là tổng khoảng cách nhỏ nhất tìm được, làm tròn đến $6$ chữ số sau dấu phẩy (sai số không quá $10^{-5}$).
Subtasks
- Subtask 1 (30%): $N \le 10$, tất cả các điểm nằm trên trục $Ox$.
- Subtask 2 (70%): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 4 0 0 0 4 4 0 4 4 |
11.313708 |
Community Discussion