trang chủ / đề bài / icpcwf07_e

Lấy hành lý

Đề bài

Mô tả

Lấy hành lý sau một chuyến bay có thể chẳng hề đơn giản. Vali và túi xách xuất hiện trên một băng chuyền, và hàng trăm hành khách chen nhau giành một chỗ đứng thuận lợi để tìm và lấy đồ của mình. Mới đây, Cơ quan quản lý sân bay Narita quyết định làm cho quá trình này hiệu quả hơn. Trước khi thiết kế lại khu vực nhận hành lý, họ cần một chương trình mô phỏng để xác định một hành khách bình thường sẽ hành động thế nào khi lấy hành lý. Mô phỏng này giả sử rằng hành khách luôn đi theo một đường gồm các đoạn thẳng để tới chỗ hành lý của mình trong thời gian ít nhất.

Trong bài này, băng chuyền được mô hình hóa bằng một đa giác đơn. Một kiện hành lý xuất hiện tại một điểm trên băng chuyền, rồi di chuyển dọc theo băng chuyền với vận tốc không đổi. Hành khách ban đầu đứng tại một điểm nằm ngoài đa giác băng chuyền. Ngay khi kiện hành lý xuất hiện, hành khách di chuyển với vận tốc không đổi (lớn hơn vận tốc của kiện hành lý) để lấy hành lý. Đường đi của hành khách không được cắt ngang qua băng chuyền nhưng được phép chạm vào nó; đường đi này đưa hành khách tới cùng vị trí với kiện hành lý đang di chuyển trong thời gian ít nhất.

Trong hình dưới đây, băng chuyền là đa giác ABCDEF. Kiện hành lý bắt đầu ở góc trên bên trái (điểm A) và di chuyển ngược chiều kim đồng hồ quanh đa giác như các mũi tên nhỏ. Hành khách bắt đầu ở điểm P và đi theo đường đưa anh ta và kiện hành lý tới cùng một chỗ (điểm M trên hình) trong thời gian ngắn nhất. Đường đi của hành khách là mũi tên màu đỏ. Hình này ứng với bộ test đầu tiên của ví dụ 1.

Dữ liệu vào

Dữ liệu vào gồm một hoặc nhiều bộ test, mỗi bộ test mô tả một tình huống lấy hành lý. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên N (3≤N≤100) là số đỉnh của đa giác băng chuyền. Tiếp theo là N dòng, mỗi dòng chứa một cặp số nguyên xi,yi (|xi|,|yi|≤10000) là tọa độ các đỉnh của đa giác, liệt kê theo thứ tự ngược chiều kim đồng hồ. Đa giác là đa giác đơn, tức là nó không tự cắt và không tự chạm. Sau mô tả đa giác là một dòng chứa hai số nguyên px,py (|px|,|py|≤10000) là tọa độ vị trí xuất phát của hành khách. Dòng cuối cùng của bộ test chứa hai số nguyên dương VL và VP (0<VL<VP≤10000) lần lượt là vận tốc của kiện hành lý và của hành khách. Mọi tọa độ tính bằng mét, vận tốc tính bằng mét mỗi phút.

Hành khách chắc chắn đứng ngoài đa giác băng chuyền. Kiện hành lý di chuyển ngược chiều kim đồng hồ quanh băng chuyền (theo thứ tự các đỉnh trong dữ liệu, sau đỉnh N lại tới đỉnh 1), xuất phát từ đỉnh đầu tiên của đa giác.

Sau mỗi bộ test có một dòng trống. Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số 0.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa số thứ tự của bộ test (bắt đầu từ 1) và thời gian ít nhất để hành khách tới được chỗ kiện hành lý. In theo đúng định dạng trong ví dụ (số phút và số giây cách nhau bởi dấu hai chấm), làm tròn tới giây gần nhất. Số giây luôn được in bằng đúng hai chữ số (thêm số 0 ở đầu nếu cần).

Ràng buộc

  • 3≤N≤100; |xi|,|yi|,|px|,|py|≤10000, các số đều nguyên.
  • Đa giác đơn, các đỉnh liệt kê ngược chiều kim đồng hồ; hành khách đứng ngoài đa giác (không nằm trên cạnh).
  • 0<VL<VP≤10000, các số đều nguyên.
  • Mỗi file có không quá 30 bộ test.
  • Thời gian đúng (tính bằng giây) cách mọi mốc làm tròn x.5 giây ít nhất 10−3 giây.

Ví dụ

Input Output Giải thích
6
0 40
0 0
20 0
20 20
40 20
40 40
120 40
70 100

4
0 0
10 0
10 10
0 10
100 100
10 11

0
Case 1: Time = 1:02
Case 2: Time = 12:36
Bộ 1 là hình vẽ ở trên. Bộ 2: hành khách đi tới đỉnh (10,0) rồi dọc theo cạnh đáy, gặp kiện hành lý ở vòng thứ tư sau khoảng 12.597 phút.
8
0 0
30 0
30 30
20 30
20 10
10 10
10 30
0 30
15 20
1 2

3
0 0
6 0
0 8
-10 8
3 5

0
Case 1: Time = 27:04
Case 2: Time = 3:15
Bộ 1: hành khách đứng trong hốc của băng chuyền hình chữ U, phải ra khỏi hốc qua góc (20,30), đi tới (30,30), xuống (30,0) rồi gặp kiện hành lý tại (27.06,0) sau khoảng 27.06 phút. Bộ 2: hành khách không nhìn thấy cạnh huyền từ phía ngoài, đi tới (0,8) (10 mét) rồi dọc cạnh huyền 6.25 mét, gặp kiện hành lý tại (3.75,3) đúng lúc 3.25 phút.

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