Hành Trình Khứ Hồi
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên mặt phẳng $Oxy$ có $N$ thành phố tại các tọa độ nguyên $(x_i, y_i)$ với các hoành độ $x_i$ đôi một phân biệt.
Một hành trình khứ hồi hợp lệ bắt đầu từ thành phố có hoành độ nhỏ nhất, đi qua một số thành phố theo thứ tự tăng dần của hoành độ để đến thành phố có hoành độ lớn nhất, sau đó quay trở về thành phố xuất phát theo thứ tự giảm dần của hoành độ, sao cho mỗi thành phố còn lại được thăm đúng một lần.
Hãy tìm tổng độ dài Euclid nhỏ nhất của một hành trình khứ hồi hợp lệ.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 1500$).
- $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^6$). Các giá trị $x_i$ đôi một khác nhau.
Kết quả
- In ra một số thực duy nhất là tổng độ dài nhỏ nhất của hành trình, làm tròn đến $6$ chữ số sau dấu phẩy.
Subtasks
- Subtask 1 (30%): $N \le 20$.
- Subtask 2 (70%): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 3 0 0 1 1 2 0 |
4.828427 |
Community Discussion