COCI 2020/2021 - Contest 2 - Odasiljaci

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đá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 ~r~. 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 ≤ N ≤ 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 ≤ x_i, y_i ≤ 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 Input1

2
1 1
2 2

Sample Output1

0.7071068

Sample Input2

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

Sample Output2

1.4142135

Sample Input3

4
2020 20
20 2020
2020 2020
20 20

Sample Output3

1000.0000000

Giải thích cho ví dụ 2

Subtask

~50~% số test có ~1 \leq N \leq 100~

Số test còn lại không có ràng buộc gì thêm


Comments

Please read the guidelines before commenting.


There are no comments at the moment.