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 cm. Coi kích thước của Carl bằng 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 từ trục ) và là góc thiên đỉnh (góc giữa tia từ gốc tọa độ tới điểm và trục ), 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 , , , . 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ố .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ ) 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
- , .
- Mỗi file có không quá 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 và trục , đi dọc cạnh dài . Bộ 2: từ đỉnh trên trục tới trung điểm cạnh nối đỉnh trên trục và đỉnh trên trục , là đường trung tuyến của một mặt, dài . Bộ 3: từ đỉnh trên (trục dương) tới đỉnh dưới, đi qua hai mặt, dài . |
| 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 . 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