Chặn giấy
Đề bài
Mô tả
Công ty của bạn sản xuất các chặn giấy nghệ thuật. Mỗi chặn giấy là hợp của hai tứ diện có chung một mặt. Chúng được làm bằng thủy tinh đặc trong suốt, bên trong có gắn các hạt màu nhỏ. Một trong các hạt nhỏ đó thực ra là một con chip RFID rất nhỏ. Con chip này phải được đặt gần một máy tính đi kèm thì máy tính đó mới hoạt động được. Thông thường điều này được thực hiện bằng cách đặt chặn giấy lên nóc máy tính. Tuy nhiên tầm hoạt động của con chip có hạn, nên khoảng cách từ chip tới mặt phẳng nóc máy tính rất quan trọng. Vì vậy cần tính khoảng cách nhỏ nhất và lớn nhất có thể từ chip tới nóc máy tính khi chặn giấy được đặt ở một vị trí đủ vững. Một vị trí được coi là đủ vững nếu chặn giấy vẫn không dịch chuyển khi trọng tâm của nó bị dời đi một khoảng tối đa đơn vị theo bất kỳ hướng nào. Có thể giả sử chặn giấy có khối lượng riêng đồng đều và con chip đủ nhỏ để coi là một điểm.

Hình 1

Hình 2
Ví dụ, xét một chặn giấy có các đỉnh của mặt chung là , , , đỉnh thứ tư của một tứ diện là , đỉnh thứ tư của tứ diện còn lại là , và con chip ở (xem Hình 1, con chip được vẽ bằng chấm nhỏ). Đặt chặn giấy với mặt nằm trên máy tính cho khoảng cách lớn nhất, xấp xỉ (phần trên của Hình 2). Đặt chặn giấy với mặt nằm trên máy tính cho khoảng cách nhỏ nhất là (phần dưới của Hình 2). Đặt chặn giấy với mặt nằm trên máy tính cho khoảng cách chỉ nhưng vị trí đó không đủ vững.
Dữ liệu vào
Dữ liệu vào gồm một hoặc nhiều bộ test. Mỗi bộ test nằm trên một dòng, mô tả sáu điểm , , , , và theo đúng thứ tự đó. Mỗi điểm được mô tả bằng ba số nguyên , , là tọa độ của nó. Hai tứ diện và đều có thể tích dương, và nằm ở hai phía khác nhau của mặt phẳng đi qua , , , và điểm nằm hẳn bên trong chặn giấy. Luôn tồn tại ít nhất một cách đặt chặn giấy ở vị trí đủ vững.
Dữ liệu vào kết thúc bằng một dòng chỉ chứa số nguyên .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test, tiếp theo là khoảng cách nhỏ nhất và lớn nhất từ con chip tới mặt phẳng đáy (nóc máy tính) khi chặn giấy được đặt ở vị trí đủ vững. Các số này được làm tròn và in với đúng năm 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 tọa độ có giá trị tuyệt đối không vượt quá .
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 0 0 0 9 0 0 0 8 0 0 0 9 1 1 -8 1 2 -1 0 0 0 7 0 0 0 7 0 0 0 7 -1 -2 -3 2 2 2 1 2 3 6 2 3 -2 6 3 -1 0 7 4 1 -2 -1 5 3 0 |
Case 1: 1.00000 3.73526 Case 2: 0.57735 2.66967 Case 3: 0.28214 5.00871 |
Bộ 1 là ví dụ trong đề (Hình 1 và Hình 2). Bộ 3: con chip nằm trên mặt chung , vẫn ở bên trong chặn giấy. |
| 0 0 0 6 0 0 4 7 0 7 0 6 0 0 -6 4 2 1 0 0 0 6 0 0 0 6 0 -1 -1 3 -1 -1 -3 1 0 1 0 |
Case 1: 1.03115 2.00000 Case 2: 0.70711 2.53993 |
Bộ 1: , , , cùng nằm trên mặt phẳng , chân đế là tứ giác có bốn đỉnh đó. Trọng tâm chiếu xuống tại , cách mọi cạnh của tứ giác hơn , nên vị trí này đủ vững và cho khoảng cách lớn nhất (điểm chiếu nằm trên cạnh của các tam giác , và rất gần cạnh , nên không thể chỉ xét từng tam giác). Bộ 2: hợp hai tứ diện không lồi, chặn giấy có thể nằm trên mặt (không phải mặt của tứ diện nào), cho khoảng cách nhỏ nhất . |
Bình luận