Khu bảo tồn gấu trúc
Đề bài
Mô tả
Tháng trước, tỉnh Tứ Xuyên đã nhận được kinh phí để xây dựng Vườn quốc gia Gấu trúc lớn, một khu bảo tồn thiên nhiên dành cho quần thể hơn con gấu trúc khổng lồ. Khu bảo tồn sẽ được bao quanh bởi một hàng rào hình đa giác. Để các nhà nghiên cứu theo dõi được gấu trúc, mỗi đỉnh của đa giác bao quanh sẽ được đặt một máy thu không dây và mỗi con vật sẽ được gắn một máy phát không dây. Mỗi máy thu phủ sóng một vùng hình tròn có tâm tại vị trí đặt máy, và mọi máy thu có cùng bán kính phủ sóng. Tất nhiên máy thu có bán kính nhỏ hơn thì rẻ hơn, nên mục tiêu của bạn là tìm bán kính phủ sóng nhỏ nhất đủ để phủ toàn bộ khu bảo tồn.
Ví dụ, Hình 1 thể hiện khu bảo tồn trong ví dụ thứ nhất. Có thể thấy bán kính là không đủ (hình a), còn bán kính tối ưu phủ được toàn bộ khu bảo tồn (hình b).

Hình 1: Minh họa ví dụ thứ nhất. (a) Bán kính không đủ để phủ khu bảo tồn. (b) Bán kính nhỏ nhất phủ được khu bảo tồn.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên () là số đỉnh của đa giác bao quanh khu bảo tồn. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và () là tọa độ của các đỉnh đa giác, liệt kê theo thứ tự ngược chiều kim đồng hồ.
Đa giác là đa giác đơn: các đỉnh đôi một khác nhau 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ủa chúng.
Dữ liệu ra
In ra bán kính phủ sóng nhỏ nhất đủ để phủ toàn bộ khu bảo tồn (gồm cả phần bên trong và biên của đa giác). Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá .
Ràng buộc
- .
- , tọa độ là số nguyên.
- Các đỉnh được cho theo thứ tự ngược chiều kim đồng hồ và tạo thành một đa giác đơn.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 0 0 170 0 140 30 60 30 0 70 |
50.000000000 | Hình 1: với bán kính còn những vùng của khu bảo tồn không được phủ, bán kính nhỏ nhất là . |
| 5 0 0 170 0 140 30 60 30 0 100 |
51.538820320 | Giống ví dụ thứ nhất nhưng đỉnh cuối ở . |
| 5 0 0 1 2 1 5 0 2 0 1 |
1.581138830 | Đa giác không lồi, có đỉnh lõm vào trong. |
Bình luận