trang chủ / đề bài / icpcwf18_g

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 1800 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 35 là không đủ (hình a), còn bán kính tối ưu 50 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 n (3≤n≤2000) là số đỉnh của đa giác bao quanh khu bảo tồn. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên x và y (|x|,|y|≤104) là tọa độ (x,y) 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á 10−6.

Ràng buộc

  • 3≤n≤2000.
  • |x|,|y|≤104, 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 35 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à 50.
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 ở (0,100).
5
0 0
1 2
1 5
0 2
0 1
1.581138830 Đa giác không lồi, có đỉnh (0,2) lõm vào trong.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0