WAVE - Phủ sóng
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Dự kiến xây dựng mạng lưới phát thanh, truyền hình ở một địa phương nọ có một đài phát và trạm tiếp sóng đánh số từ 1 tới n. Trạm thứ i đã được xây dựng ở toạ độ ( x i , y i ). Để đảm bảo tính trung thực của các nguồn tin, các trạm tiếp sóng chỉ có thể nhận tín hiệu trực tiếp từ đài phát. Và như vậy có nghĩa là để phát sóng đến tất cả các trạm thu, bán kính phủ sóng của đài phát phải đủ lớn để phủ hết các trạm tiếp sóng. (Giả sử vùng phủ sóng là hình tròn có tâm là đài phát).
Yêu cầu: Hãy tìm vị trí đặt đài phát sao cho khoảng cách từ trạm thu xa nhất tới đài phát là ngắn nhất. Cho biết bán kính phủ sóng trong phương án tìm được tối thiểu phải là bao nhiêu.
Dữ liệu:
- Dòng đầu: Chứa số nguyên dương n( 0 < n <= 200 );
- Dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ( x i , y i ) có giá trị tuyệt đối không quá 10000 cách nhau ít nhất một dấu cách.
Kết quả:
Ghi ra bán kính nhỏ nhất tìm được, làm tròn tới 6 chữ số sau dấu chấm thập phân
Ví dụ
Input
8
0 0
200 300
200 0
200 200
0 200
100 300
300 100
100 0
Output
182.107840
- Người up: franco1
- Nguồn bài: Thầy Lê Minh Hoàng