Đường đi Hamilton trên đa giác lồi
Đề bài
Mô tả
Đội The Mafia đang duyệt các đề bài đề xuất cho một kỳ thi ICPC. Một trong các đề được đề xuất như sau:
Đường đi Hamilton
Cho một đồ thị vô hướng đầy đủ có trọng số gồm đỉnh, đánh số từ đến . Khoảng cách giữa đỉnh và đỉnh là .
Một đường đi Hamilton trong đồ thị là một đường đi qua mỗi đỉnh đúng một lần. Độ dài của đường đi là tổng trọng số các cạnh mà nó sử dụng.
Hãy tìm đường đi Hamilton ngắn nhất, tức là tìm một hoán vị của sao cho nhỏ nhất.
"Nhưng khoan, bài này chẳng phải quá kinh điển sao?", Quang, một thành viên của đội The Mafia, nghĩ thầm. Sau một hồi suy nghĩ về đường đi Hamilton, Quang đưa ra một biến thể như sau: các đỉnh nằm ở các đỉnh của một đa giác lồi trên mặt phẳng, được liệt kê theo thứ tự ngược chiều kim đồng hồ, và khoảng cách giữa đỉnh và đỉnh là khoảng cách Euclid giữa hai đỉnh đó.
Biến thể này đủ thú vị (và hy vọng là chưa từng xuất hiện ở kỳ thi lập trình nào khác) nên được đội chấp nhận và trở thành bài H của kỳ thi. Là những thí sinh tài năng, bạn có giải được bài này không?
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa số nguyên (): số đỉnh.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (): tọa độ của đỉnh thứ .
Dữ liệu đảm bảo:
- Tọa độ các đỉnh là các đỉnh của một đa giác lồi, được liệt kê theo thứ tự ngược chiều kim đồng hồ.
- Không có ba đỉnh liên tiếp nào thẳng hàng.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra số nguyên : chỉ số các đỉnh theo thứ tự trên đường đi Hamilton ngắn nhất. Dãy phải là một hoán vị của .
Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối giữa độ dài đường đi của bạn và độ dài đường đi của ban giám khảo không vượt quá . Cụ thể, gọi là độ dài đường đi của bạn và là độ dài đường đi của ban giám khảo, đáp án được chấp nhận khi và chỉ khi .
Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- .
- , .
- Các đỉnh tạo thành đa giác lồi theo thứ tự ngược chiều kim đồng hồ, không có ba đỉnh liên tiếp thẳng hàng.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 4 3 1 4 1 1 3 1 8 2 4 1 3 1 2 2 1 3 1 4 2 4 3 3 4 |
1 4 3 2 8 1 2 3 4 5 6 7 |
Bộ dữ liệu thứ nhất: đường đi có độ dài . Bộ dữ liệu thứ hai: đường đi đi dọc biên đa giác, độ dài . |
| 2 3 0 0 5 0 0 5 6 0 1 4 0 8 1 8 2 4 3 0 2 |
3 1 2 1 6 5 2 3 4 |
Ví dụ bổ sung (không có trong đề gốc). Bộ dữ liệu thứ nhất: độ dài . Bộ dữ liệu thứ hai: đường đi đi zíc zắc qua đa giác, độ dài , ngắn hơn mọi đường đi dọc biên (ngắn nhất là ). |
Bình luận