Giải pháp ô nhiễm
Đề bài
Mô tả
Là nhân viên của công ty Aqueous Contaminate Management, bạn phải theo dõi lượng chất ô nhiễm bị đổ (đôi khi vô tình, đôi khi cố ý) xuống sông, hồ và biển. Một trong các nhiệm vụ của bạn là đo mức độ ảnh hưởng của ô nhiễm lên các hệ sinh thái dưới nước như rạn san hô, bãi đẻ trứng, v.v.

Mô hình phân tích được minh họa trong hình trên (ứng với ví dụ thứ nhất). Bờ biển (đường nằm ngang trong hình) nằm trên trục , nguồn ô nhiễm đặt tại gốc tọa độ . Vùng ô nhiễm lan ra mặt nước được biểu diễn bằng nửa hình tròn tâm tại gốc tọa độ, bán kính , nằm phía trên trục ; còn đa giác biểu diễn hệ sinh thái cần quan tâm. Bạn cần tính diện tích phần hệ sinh thái bị ô nhiễm, tức là phần được tô màu xanh đậm trong hình.
Dữ liệu vào
Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên và , lần lượt là số đỉnh của đa giác và bán kính của vùng ô nhiễm. Tiếp theo là dòng, dòng thứ chứa hai số nguyên là tọa độ đỉnh thứ của đa giác, các đỉnh được liệt kê theo thứ tự ngược chiều kim đồng hồ.
Dữ liệu ra
In ra diện tích phần đa giác nằm trong nửa hình tròn tâm tại gốc tọa độ, bán kính . Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá .
Ràng buộc
- .
- .
- , .
- Đa giác không tự cắt và không tự chạm.
- Không có đỉnh nào nằm trên đường tròn biên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 10 -8 2 8 2 8 14 0 14 0 6 -8 14 |
101.576437872 | Đa giác và nửa hình tròn như trong hình, phần bị ô nhiễm là vùng tô màu. |
| 3 5 0 0 7 1 -1 7 |
19.634954085 | Cạnh từ tới tiếp xúc với đường tròn tại , nên phần bị ô nhiễm là hình quạt góc vuông giữa hai cạnh xuất phát từ gốc tọa độ: diện tích . |
Bình luận