Bão đang đến
Đề bài
Mô tả
Aroma sống trên một hòn đảo giữa biển. Đang là mùa bão và Aroma cần chỉ đạo công tác dọn dẹp sau mỗi cơn bão, vì vậy cô muốn biết trước diện tích vùng bị ảnh hưởng bởi từng cơn bão.
Aroma mô hình hoá hòn đảo thành một đa giác đơn có đỉnh và cạnh. Đa giác có thể không lồi nhưng không tự cắt.
Có cơn bão sắp tới. Mỗi cơn bão là một hình tròn di chuyển và có bán kính thay đổi. Cụ thể:
- Cơn bão được mô hình hoá thành một hình tròn, tâm là mắt bão và bán kính là phạm vi ảnh hưởng.
- Cơn bão xuất hiện với tâm tại điểm và bán kính .
- Tâm bão di chuyển dần theo đường thẳng từ đến , đồng thời bán kính thay đổi dần từ đến . Chính xác hơn, tại một thời điểm, nếu khoảng cách từ tâm bão hiện tại đến là và đến là thì bán kính hiện tại của bão là .
- Khi tâm bão đến điểm , nó dừng ở đó cho đến khi tan.
Nếu tại một thời điểm nào đó, một điểm trên đảo nằm trong hình tròn biểu diễn cơn bão thứ thì được gọi là bị ảnh hưởng bởi cơn bão này.
Hãy giúp Aroma tính diện tích phần đảo bị ảnh hưởng bởi mỗi cơn bão.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số bộ test (). Mỗi bộ test có dạng:
- Dòng đầu tiên chứa số nguyên (): số đỉnh của đa giác biểu diễn hòn đảo.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên , (): toạ độ đỉnh thứ của đa giác.
- Dòng tiếp theo chứa số nguyên (): số cơn bão sắp tới.
- Dòng thứ trong dòng tiếp theo chứa sáu số nguyên (, ) mô tả cơn bão thứ .
Dữ liệu đảm bảo:
- các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ;
- không có hai đỉnh nào trùng toạ độ;
- hai cạnh của đa giác chỉ giao nhau tại đỉnh chung của chúng (nếu có);
- tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi cơn bão, in ra diện tích phần đảo bị ảnh hưởng trên một dòng. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá : gọi đáp án của bạn là và đáp án của ban giám khảo là , đáp án được chấp nhận khi và chỉ khi .
Ràng buộc
- ,
- ,
- Tổng trên tất cả các bộ test không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 0 0 0 3 4 0 5 0 0 4 0 0 4 0 0 1 0 3 1 0 0 2 4 0 2 1 1 1 5 5 5 -1 -1 1 3 3 3 5 0 0 1 1 2 2 2 0 2 -2 1 2 0 1 6 0 2 3 3 3 2 1 1 1 1 2 2 1 2 2 1 |
6.000000000000 2.625000000000 5.333333333333 5.785398163397 5.982317997582 1.576314961400 0.863647609001 |
Bộ test thứ nhất: hòn đảo là tam giác vuông có diện tích . Cơn bão thứ nhất đứng yên tại với bán kính nên phủ toàn bộ đảo. Cơn bão thứ hai quét một dải rộng dọc trục tung từ đến . |
| 1 4 0 0 4 0 4 4 0 4 3 2 2 1 2 2 1 -2 2 1 6 2 1 2 2 100 2 2 1 |
3.141592654 8.000000000 16.000000000 |
Hòn đảo là hình vuông cạnh . Cơn bão thứ nhất đứng yên, ảnh hưởng một hình tròn bán kính (diện tích ). Cơn bão thứ hai quét ngang dải qua toàn bộ đảo (diện tích ). Cơn bão thứ ba ban đầu đã phủ toàn bộ đảo. |
Bình luận