trang chủ / đề bài / icpcwf08_c

Dây cuaroa

Đề bài

Mô tả

Nhiều hệ thống cơ khí hoạt động nhờ các trục quay được nối với nhau bằng dây cuaroa (băng chuyền). Các trục có kích thước khác nhau và quay theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Cách dây nối hai trục phụ thuộc vào chiều quay của chúng, như trong Hình 1 và Hình 2.

Hình 1: hai trục cùng chiều quay (được phép).

Hình 2: hai trục ngược chiều quay (được phép).

Hình 3: dây tự cắt chính nó (bị cấm).

Hình 4: dây đi xuyên qua một trục khác (bị cấm).

Một nhiệm vụ khi lắp đặt các hệ thống như vậy là nối hai trục cho trước với nhau, thỏa mãn các ràng buộc sau:

  • Nếu hai trục được nối quá xa nhau, dây có thể rung hỗn loạn khi bị tác động nhẹ. Để tránh điều đó, chỉ được nối hai trục khi khoảng cách giữa điểm dây rời trục này và điểm dây chạm trục kia nhỏ hơn một giá trị d (d phụ thuộc vào loại dây).
  • Dây không được tự cắt chính nó, như trong Hình 3.
  • Dây không được đi xuyên qua một trục khác (hoặc chạm vào một trục quay sai chiều), như trong Hình 4.
  • Dây không phải là một vòng kín: nó chỉ đi theo một chiều, từ trục bắt đầu đến trục kết thúc. Trục bắt đầu "đẩy" dây và trục kết thúc "kéo" dây.

Hình 5: nối trục A (Start) với trục D (End).

Ví dụ, xét bài toán nối trục A với trục D trong Hình 5. Giả sử khoảng cách cần thiết để nối A với C (đường nét đứt màu xanh) hoặc nối B với D lớn hơn giới hạn cho phép. Khi đó cách nối ngắn nhất từ A đến D là đường nét liền, đi từ trục A đến B, đến C rồi đến D. Lưu ý rằng không thể đi từ B đến E rồi đến D vì khi đó dây sẽ tự cắt chính nó.

Hãy viết chương trình tính độ dài nhỏ nhất của dây nối hai trục cho trước. Dây đi qua mỗi trục nhiều nhất một lần.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên N là số trục, các trục được đánh số từ 0 đến N−1. Bắt đầu từ dòng tiếp theo là N bộ bốn có dạng x y r s, trong đó x, y là tọa độ nguyên của tâm trục, r là bán kính nguyên của trục, s là C nếu trục quay theo chiều kim đồng hồ hoặc CC nếu quay ngược chiều kim đồng hồ. Chiều dương của trục x hướng sang phải, chiều dương của trục y hướng lên trên. Bộ bốn đầu tiên mô tả trục 0, bộ thứ hai mô tả trục 1, và cứ thế. Các bộ bốn có thể trải trên nhiều dòng, nhưng không bộ bốn nào bị tách ra hai dòng. Không có hai trục nào chạm nhau hoặc chồng lên nhau. Dòng cuối của mỗi bộ test chứa hai số nguyên i và j là chỉ số trục bắt đầu và trục kết thúc, tiếp theo là số thực d là giới hạn khoảng cách.

Sau bộ test cuối cùng là một dòng chứa duy nhất số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ 1) và độ dài của đường nối ngắn nhất, theo định dạng Case k: length = L. Nếu không thể nối tới trục kết thúc, in Case k: Cannot reach destination shaft. Xem định dạng trong ví dụ.

Khi đo độ dài, bắt đầu từ điểm dây rời trục bắt đầu lần đầu tiên và kết thúc tại điểm dây chạm trục kết thúc lần đầu tiên. Độ dài phải gồm cả các đoạn dây giữa các trục lẫn phần dây vòng quanh các trục trung gian. Đáp án được làm tròn đến hàng phần trăm, không bắt buộc in các chữ số 0 thừa ở cuối phần thập phân.

Ràng buộc

  • 2≤N≤20, 0≤i,j≤N−1, i≠j.
  • 0≤x,y≤10000, 0<r≤1000.
  • 0<d≤20000, d có nhiều nhất một chữ số sau dấu thập phân.
  • Mỗi file có không quá 30 bộ test.
  • Dữ liệu đảm bảo không có trường hợp sát biên: không đoạn dây nào tiếp xúc với một trục khác, không đoạn dây nào có độ dài xấp xỉ d, các kết luận về việc hai đoạn dây cắt nhau không thay đổi khi tọa độ thay đổi một lượng rất nhỏ, và đáp án không nằm sát mốc làm tròn.

Ví dụ

Input Output Giải thích
5
24 50 14 C 93 78 20 C 118 8 15 CC
167 32 13 C 159 88 15 CC
0 3 82.5
5
24 50 14 C 93 78 20 C 118 8 15 CC
167 32 13 C 159 88 15 C
0 3 82.5
5
24 50 14 C 93 78 20 C 118 8 15 CC
167 32 13 C 159 88 15 C
0 3 8.5
0
Case 1: length = 271
Case 2: length = 228.23
Case 3: Cannot reach destination shaft
Bộ 1 và bộ 2 khác nhau ở chiều quay của trục 4. Ở bộ 3, d=8.5 quá nhỏ nên không nối được. Độ dài 270.996… được làm tròn thành 271.
2
0 0 10 C 50 0 10 C
0 1 100
2
0 0 10 C 50 0 10 CC
0 1 100
3
0 0 10 C 100 0 10 C 50 3 20 CC
0 1 1000
0
Case 1: length = 50
Case 2: length = 45.83
Case 3: length = 103.51
Bộ 1: hai trục cùng chiều, dây là tiếp tuyến chung ngoài phía trên, dài 50. Bộ 2: hai trục ngược chiều, dây là tiếp tuyến chung trong, dài 502−202≈45.83. Bộ 3: tiếp tuyến chung ngoài từ trục 0 đến trục 1 đi xuyên qua trục 2, nên dây phải đi 0→2→1 và vòng quanh trục 2.

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