Vòng Tròn Bao Phủ Nhỏ Nhất
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Cần lắp đặt một trạm phát sóng Wi-Fi phủ sóng tới toàn bộ $N$ ngôi nhà trên mặt phẳng tọa độ.
Hãy tìm bán kính nhỏ nhất của một hình tròn sao cho tất cả $N$ điểm đều nằm bên trong hoặc trên đường biên của hình tròn đó (bằng thuật toán Welzl trong $O(N)$ kỳ vọng).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($|x_i|, |y_i| \le 10^6$).
Dữ liệu ra
- In ra một số thực là bán kính nhỏ nhất của hình tròn bao phủ, làm tròn đến $6$ chữ số thập phân.
Ví dụ
| Input | Output |
|---|---|
| 3 0 0 4 0 0 3 |
2.500000 |
Giới hạn
- $1 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^6$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion