Những hòn đảo nhìn từ trên trời
Đề bài
Mô tả
Có thể bạn chưa bao giờ nghe nói tới quần đảo Iceepeecee, nhưng cư dân ở đó lại thấy như vậy là rất tốt. Nằm ở một vùng xa xôi của Nam Thái Bình Dương, quần đảo thật sự cách biệt với thế giới, không có tuyến hàng không hay đường biển thường xuyên nào, và vẫn là một thiên đường nhiệt đới với hệ động thực vật bản địa còn nguyên vẹn.
Không có tên trên bản đồ thì rất tốt khi bạn không muốn bị khách du lịch kéo tới ồ ạt, nhưng lại không hay chút nào khi bạn thật sự cần một tấm bản đồ. Một lý do như vậy vừa xuất hiện: chính quyền trung ương của Iceepeecee cần một bản đồ chính xác của các hòn đảo để phân bổ ngân sách. Thiên đường nhiệt đới cũng cần tiền, nên Iceepeecee cần một tấm bản đồ!
Cách dễ nhất để vẽ bản đồ là khảo sát từ trên không. Sau khi gạt bỏ việc thuê máy bay vì quá đắt, đóng khinh khí cầu vì quá nguy hiểm và gắn máy ảnh cho chim bồ câu đưa thư vì quá tàn nhẫn với động vật, họ nảy ra một ý tưởng tuyệt vời. Dù quần đảo nằm ở nơi hẻo lánh, vẫn có rất nhiều chuyến bay thương mại bay ngang qua bầu trời Iceepeecee. Vậy tại sao không gắn máy ảnh lên những chuyến bay vốn đã được lên lịch sẵn? Đó sẽ là một giải pháp rẻ!
Kế hoạch của Iceepeecee là lắp máy ảnh quét dòng lên các máy bay. Máy ảnh này hướng thẳng xuống dưới và chụp ảnh từng đoạn thẳng một, đoạn thẳng này vuông góc với đường bay. Đoạn thẳng được chụp phụ thuộc vào độ cao của máy bay và góc mở của máy ảnh (xem Hình 1): máy ảnh nhìn thấy phần mặt đất nằm trong góc về mỗi bên so với phương thẳng đứng. Góc càng lớn thì máy ảnh nhìn thấy càng nhiều, nhưng máy ảnh cũng càng đắt.

Hình 1: Máy bay nhìn từ phía trước. Máy ảnh hướng xuống dưới và nhìn thấy phần mặt đất bên dưới máy bay được tô màu xanh lá. Phần nhìn thấy được nhiều hay ít phụ thuộc vào góc mở .
Hơn nữa, Iceepeecee muốn chắc chắn rằng mỗi hòn đảo được chụp trọn vẹn bởi ít nhất một chuyến bay. Nghĩa là nếu một hòn đảo chỉ được chụp một phần bởi nhiều chuyến bay khác nhau thì không đủ, kể cả khi ghép các ảnh lại sẽ phủ kín cả hòn đảo.
Mỗi đường bay là một đoạn thẳng trong không gian ba chiều, từ tới (xem Hình 2), trong đó tọa độ là độ cao của máy bay. Ảnh chỉ được chụp dọc theo các đoạn thẳng này.

Hình 2: Khảo sát ba hòn đảo bằng hai đường bay, ứng với ví dụ thứ nhất. (a) Ba hòn đảo (màu đen) và hai đường bay (đỏ và xanh lá), không thể hiện độ cao. (b) Vùng tô màu là phần mặt đất nhìn thấy được trên hai đường bay với góc được chọn tối ưu.
Cho vị trí các hòn đảo và các chuyến bay, Iceepeecee muốn tìm góc mở nhỏ nhất cho phép khảo sát thành công. Bạn hãy giúp họ!
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (): số hòn đảo và số đường bay.
Tiếp theo là mô tả của hòn đảo. Mô tả hòn đảo thứ bắt đầu bằng một dòng chứa số nguyên (), số đỉnh của đa giác mô tả hòn đảo. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên () là tọa độ các đỉnh của hòn đảo thứ theo thứ tự ngược chiều kim đồng hồ. Đa giác của mỗi hòn đảo là đa giác đơn: các đỉnh đôi một phân biệt và không có hai cạnh nào cắt nhau hay chạm nhau, ngoại trừ hai cạnh liên tiếp chạm nhau tại đỉnh chung. Các hòn đảo khác nhau không cắt nhau và không chạm nhau.
Cuối cùng là dòng, mỗi dòng mô tả một đường bay gồm sáu số nguyên (, và ): chuyến bay đi từ tới .
Dữ liệu ra
In ra góc nhỏ nhất (tính bằng độ) cho phép khảo sát trọn vẹn mọi hòn đảo bằng các chuyến bay đã cho. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá . Nếu không có góc nào như vậy, in ra impossible.
Dữ liệu vào được chọn sao cho nếu thay đổi tọa độ các đỉnh của các hòn đảo một lượng không quá thì đáp án thay đổi không quá sai số cho phép.
Ràng buộc
- ; .
- ; mỗi hòn đảo là một đa giác đơn cho theo thứ tự ngược chiều kim đồng hồ; các hòn đảo không cắt nhau, không chạm nhau.
- , , .
- Tất cả các số trong dữ liệu vào là số nguyên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 3 20 30 50 50 10 50 4 40 20 60 10 75 20 60 30 4 45 60 55 55 60 60 55 65 0 30 20 78 70 5 55 0 20 70 60 10 |
48.031693036 | Hình 2. Đường bay thứ nhất (đỏ) chụp trọn tam giác khi và hòn đảo thứ ba khi . Hòn đảo thứ hai cần với đường bay thứ nhất nhưng chỉ cần với đường bay thứ hai (xanh lá), nên đáp án là . |
| 1 1 4 0 0 10 0 10 10 0 10 5 5 10 15 5 10 |
impossible | Chuyến bay chỉ chụp phần mặt đất nằm giữa hai đường thẳng vuông góc với đường bay tại hai đầu mút và . Đỉnh nằm ngoài phần đó nên dù lớn tới đâu hòn đảo cũng không được chụp trọn vẹn. |
Bình luận