Bao lồi bo tròn
Đề bài
Mô tả
Trên mặt phẳng tọa độ có hình tròn và đa giác. Hãy tính chu vi bao lồi của tất cả các hình này, tức là chu vi của hình lồi nhỏ nhất chứa toàn bộ các hình tròn và các đa giác.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (, ): số hình tròn và số đa giác.
- dòng tiếp theo, mỗi dòng chứa ba số thực , và : tâm và bán kính của một hình tròn (, ).
- dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên () là số đỉnh của đa giác, tiếp theo là cặp số thực là tọa độ các đỉnh (). Tổng số đỉnh của tất cả các đa giác không vượt quá .
Dữ liệu ra
In ra chu vi của bao lồi. Kết quả được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án không vượt quá .
Ràng buộc
- , .
- , .
- , tổng các không vượt quá , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 -14.123000 -1.456000 5.789000 0.123000 14.456000 4.789000 -6.868686 20.456780 3.789285 1 5.123000 5.456000 2 6.879000 6.123000 7.456000 7.789000 |
88.888888 | Ba hình tròn, một đa giác chỉ có một đỉnh và một đa giác có hai đỉnh (một đoạn thẳng). |
| 1 1 0.000000 0.000000 1.000000 1 2.000000 0.000000 |
7.652892 | Ví dụ bổ sung (không có trong đề gốc). Bao lồi gồm hai tiếp tuyến từ điểm tới đường tròn đơn vị, mỗi đoạn dài , và cung tròn : chu vi . |
Bình luận