Máy thổi tuyết
Đề bài
Mô tả
Cho một đa giác đỉnh trên mặt phẳng và một điểm nằm ngoài đa giác (không nằm trong và không nằm trên biên). Đa giác được quay trọn một vòng quanh điểm : mỗi điểm thuộc đa giác (kể cả các điểm trên biên) di chuyển trên một đường tròn tâm .
Hãy tính diện tích vùng mặt phẳng mà đa giác quét qua trong quá trình quay.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên , , : số đỉnh của đa giác và tọa độ điểm .
- dòng tiếp theo, mỗi dòng gồm hai số nguyên , : tọa độ các đỉnh của đa giác, liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
Đa giác là đa giác đơn (có thể không lồi) và không có ba đỉnh liên tiếp nào thẳng hàng.
Dữ liệu ra
In ra một số thực là diện tích vùng bị quét. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá .
Ràng buộc
- Điểm nằm ngoài đa giác
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 0 0 1 -1 2 1 2 |
12.5663706144 | Điểm gần nhất của tam giác là , cách một khoảng ; điểm xa nhất là , cách một khoảng . Vùng quét là hình vành khăn có diện tích . |
| 4 1 -1 0 0 1 2 2 0 1 1 |
21.9911485751 | Đa giác không lồi. Điểm gần nhất là hoặc với bình phương khoảng cách ; điểm xa nhất là với bình phương khoảng cách . Diện tích là . |
Bình luận