Vòng Tròn Bao Phủ Nhỏ Nhất

Buổi 61 — Hình học tính toán
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề 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
Draft saved