trang chủ / đề bài / icpc25_reg_h

Đườ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 n đỉnh, đánh số từ 1 đến n. Khoảng cách giữa đỉnh i và đỉnh j là wi,j.

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ị p1,p2,…,pn của {1,2,…,n} sao cho ∑i=1n−1wpi,pi+1 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 i và đỉnh j 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 τ (1≤τ≤1000). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa số nguyên n (3≤n≤3000): số đỉnh.
  • Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên xi và yi (0≤xi,yi≤106): tọa độ của đỉnh thứ i.

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 n qua tất cả các bộ dữ liệu không vượt quá 3000.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra n số nguyên p1,p2,…,pn: chỉ số các đỉnh theo thứ tự trên đường đi Hamilton ngắn nhất. Dãy p phải là một hoán vị của {1,2,…,n}.

Đá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á 10−6. Cụ thể, gọi P là độ dài đường đi của bạn và J là độ dài đường đi của ban giám khảo, đáp án được chấp nhận khi và chỉ khi |P−J|max(1,|J|)≤10−6.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤τ≤1000.
  • 3≤n≤3000, 0≤xi,yi≤106.
  • 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 n qua tất cả các bộ dữ liệu không vượt quá 3000.

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 1→4→3→2 có độ dài 5+2+3≈7,236. Bộ dữ liệu thứ hai: đường đi 8→1→2→…→7 đi dọc biên đa giác, độ dài 4×1+3×2≈8,243.
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 5+5=10. Bộ dữ liệu thứ hai: đường đi 1→6→5→2→3→4 đi zíc zắc qua đa giác, độ dài 1+17+3+17+1≈13,246, ngắn hơn mọi đường đi dọc biên (ngắn nhất là 2+317≈14,369).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0