Cubic UFO

Một tàu vũ trụ ngoài hành tinh hình lập phương bí ẩn xuất hiện trên bầu trời Toronto! Trong bài này, Toronto là mặt phẳng ba chiều song song với mặt phẳng \(xz\) tại \(y=-3\) km. Con tàu là khối lập phương đặc cạnh 1 km, tâm \((0,0,0)\), với tám đỉnh \((\pm0.5,\pm0.5,\pm0.5)\) km. Nó đổ một cái bóng đáng ngại xuống mặt phẳng; chính xác hơn, bóng là phép chiếu trực giao của khối lập phương lên mặt phẳng ấy, coi Mặt Trời là một điểm ở xa vô hạn phía trên theo trục \(y\).

Quân đội chấp nhận con tàu miễn là người ngoài hành tinh đáp ứng yêu cầu hành chính: bóng phải có diện tích đủ gần \(A\) km² theo định nghĩa chính xác ở phần output. Bạn, một chuyên gia ngôn ngữ học hình học, được thuê để truyền đạt yêu cầu. Con tàu không thể đổi kích thước hay dời tâm, nhưng có thể quay tùy ý tại chỗ.

Hãy tìm một phép quay để diện tích bóng gần \(A\). Biểu diễn tư thế bằng tâm của ba mặt bất kỳ sao cho không có cặp mặt nào đối nhau.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test là một dòng chứa số hữu tỉ \(A\), diện tích bóng mong muốn tính bằng km², với đúng sáu chữ số sau dấu thập phân. Đề bảo đảm mọi \(A\) hợp lệ đều có một tư thế thỏa mãn.

Dữ liệu ra

Với mỗi test, trước hết in Case #x:, rồi in ba dòng, mỗi dòng gồm ba số hữu tỉ là tọa độ \(x,y,z\) của một tâm mặt. Có thể dùng dạng thập phân hoặc khoa học.

Kết quả được chấp nhận khi và chỉ khi đồng thời thỏa mãn:

• Khoảng cách từ mỗi điểm tới gốc nằm trong \([0.5-10^{-6},0.5+10^{-6}]\) km.
• Góc giữa mọi cặp đoạn nối gốc với hai điểm nằm trong \([\pi/2-10^{-6},\pi/2+10^{-6}]\) radian.
• Bộ chấm dựng tám đỉnh dưới dạng \(\pm p_1\pm p_2\pm p_3\) (với mỗi \(p_i\) chọn cộng \(p_i\) hoặc \(-p_i\)), chiếu chúng lên mặt phẳng \(y=-3\), lấy bao lồi, rồi yêu cầu diện tích thuộc \([A-10^{-6},A+10^{-6}]\) km².

Có thể cần in hơn sáu chữ số sau dấu thập phân để an toàn. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• Mọi \(A\) đều được bảo đảm có nghiệm.

Phân nhóm

• Test Set 1 (hiển thị): \(1.000000\le A\le1.414213\).
• Test Set 2 (ẩn): \(1.000000\le A\le1.732050\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
1.000000
1.414213

Case #1:
0.5 0 0
0 0.5 0
0 0 0.5
Case #2:
0.3535533905932738 0.3535533905932738 0
-0.3535533905932738 0.3535533905932738 0
0 0 0.5

Nguồn

Google Code Jam 2018, Vòng loại, bài Cubic UFO.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.