trang chủ / đề bài / icpcwf09_c

Carl trở lại

Đề bài

Mô tả

Chú kiến Carl đã trở lại! Lần trước chúng ta gặp Carl (bài A, ICPC World Finals 2004), chú còn hơi lộn xộn, luôn đi theo những con đường ngoằn ngoèo kỳ lạ. Giờ đây Carl đã "thẳng thắn" lại, theo đúng nghĩa đen: chú luôn đi theo đường thẳng nhất, ngắn nhất giữa hai điểm bất kỳ. Nghe thì đơn giản, trừ một điều nhỏ: Carl dành phần lớn thời gian trên một cái chặn giấy có dạng bát diện đều. Bát diện đều là một trong năm khối đa diện đều Platon, gồm tám tam giác đều, như trong Hình 1.

Hình 1: Bát diện đều

Carl có khả năng bẩm sinh luôn đi theo đường ngắn nhất từ bất kỳ điểm xuất phát nào tới bất kỳ điểm đích nào trên mặt chặn giấy. Nhiệm vụ của bạn là kiểm chứng điều đó: cho hai điểm như vậy (không nhất thiết phân biệt), hãy tính độ dài đường đi ngắn nhất giữa chúng trên bề mặt chặn giấy.

Chặn giấy được cố định như nhau cho mọi bộ test: bát diện có tâm tại gốc tọa độ và mỗi đỉnh nằm trên một trục tọa độ. Mọi cạnh dài đúng 10 cm. Coi kích thước của Carl bằng 0 và bỏ qua mọi giá đỡ có thể cần để giữ chặn giấy ở đúng vị trí.

Mỗi điểm được cho bằng tọa độ cầu (θ,ϕ): như trong Hình 1, θ là góc phương vị (đo trong mặt phẳng xy từ trục x) và ϕ là góc thiên đỉnh (góc giữa tia từ gốc tọa độ tới điểm và trục z), cả hai tính bằng độ. Điểm trên chặn giấy là giao điểm của bề mặt bát diện với tia xuất phát từ gốc tọa độ theo hướng đó.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test gồm bốn số nguyên θ1, ϕ1, θ2, ϕ2. Hai số đầu là tọa độ cầu của điểm xuất phát, hai số sau là tọa độ cầu của điểm đích.

Dữ liệu vào kết thúc bằng một dòng chứa bốn số −1.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ 1) và độ dài (tính bằng cm) của đường đi ngắn nhất từ điểm xuất phát tới điểm đích, làm tròn tới phần nghìn (đúng ba chữ số sau dấu thập phân). Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 0≤θi<360, 0≤ϕi≤180.
  • Mỗi file có không quá 104 bộ test.

Ví dụ

Input Output Giải thích
0 90 90 90
0 90 90 45
0 0 0 180
-1 -1 -1 -1
Case 1: 10.000
Case 2: 8.660
Case 3: 17.321
Bộ 1: hai đỉnh kề nhau trên trục x và trục y, đi dọc cạnh dài 10. Bộ 2: từ đỉnh trên trục x tới trung điểm cạnh nối đỉnh trên trục y và đỉnh trên trục z, là đường trung tuyến của một mặt, dài 53. Bộ 3: từ đỉnh trên (trục z dương) tới đỉnh dưới, đi qua hai mặt, dài 103.
45 90 225 90
30 60 30 60
45 45 225 135
-1 -1 -1 -1
Case 1: 15.000
Case 2: 0.000
Case 3: 15.073
Bộ 1: hai điểm đối xứng qua tâm, là trung điểm của hai cạnh song song trên mặt phẳng xy. Bộ 2: điểm xuất phát trùng điểm đích. Bộ 3: hai điểm nằm trên hai mặt đối diện nhau, đường đi ngắn nhất phải đi qua các mặt trung gian.

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