Trạm Trung Chuyển Tối Ưu

Buổi 67-68 — Mock IOI
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved