[COCI2021 - Contest 02] Bài 2: Odašiljači

Xem PDF

Nộp bài

Điểm: 100 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M
Input: bàn phím
Output: màn hình

Tác giả:
Dạng bài

Đáng buồn thay, đây là lần cuối cùng Sean đóng vai James Bond.

Nhiệm vụ của anh ta là kết nối ~N~ ăng-ten nằm rải rác trên một sa mạc rộng lớn, có thể được biểu diễn dưới dạng một mặt phẳng 2D. Anh ta sẽ đặt bán kính truyền của mỗi ăng-ten cùng là một số thực không âm . Phạm vi của một ăng-ten được xác định là tập hợp tất cả các điểm có khoảng cách đến ăng-ten tối đa là ~r~ . Nếu phạm vi của hai ăng-ten có một điểm chung, các ăng-ten đó có thể kết nối trực tiếp với nhau. Ngoài ra, nếu ăng-ten ~A~ và ~B~ có thể kết nối với nhau, cũng như ăng-ten ~B~ và ~C~ , thì ăng-ten ~A~ và ~C~ cũng có thể kết nối với nhau thông qua ăng-ten ~B~ .

Sean muốn kết nối các ăng-ten, tức là hai ăng-ten bất kỳ có thể liên lạc với nhau. Vì tổ chức đã giới hạn chi tiêu của anh ấy cho nhiệm vụ này và bán kính càng lớn đòi hỏi càng nhiều tiền nên Sean sẽ chọn bán kính ~r~ nhỏ nhất có thể. Giúp anh ấy giải quyết vấn đề này!

Input

Dòng đầu chứa số nguyên ~N~ ~(1 \le N \le 1000)~ là số lượng ăng-ten ~N~ dòng tiếp theo bao gồm 2 số nguyên ~x_i,y_i~ ~(0 \le x_i,y_i \le 10^9)~ là tọa độ của ăng-ten thứ ~i~

Output

Bán kính nhỏ nhất (sai số không vượt quá ~10^{-6}~ )

Sample 1

Input

2
1 1
2 2

Output

0.7071068

Sample 2

Input

7
2 3
3 4
4 5
0 1
3 1
4 2
1 5

Output

1.4142135

Sample 3

Input

4
2020 20
20 2020
2020 2020
20 20

Output

1000.0000000

Giải thích

enter image description here

Subtask

~50~% số test có ~1 \le N \le ~

Còn lại không có ràng buộc gì thêm.


Bình luận đầu tiên

Bình luận

Không có bình luận nào.