COCI '20 Contest 2 #2 Odašiljači

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Sadly, this is the last time Sean will play James Bond.

His mission is to network nn antennas that are scattered across a vast desert, which can be represented as a 2D plane. He will set the transmission radius of each antenna to be the same non-negative real number rr. The range of an antenna is defined as the set of all points whose distance to the antenna is at most rr. If ranges of two antennas have a common point, those antennas can directly communicate. Also, if antennas AA and BB can communicate, as well as antennas BB and CC, then antennas AA and CC are also able to communicate, through antenna BB.

Sean wants to network the antennas, i.e. make it possible for every two antennas to communicate. Since MM has limited his spending for this mission, and larger radii require more money, Sean will choose the smallest possible radius rr. Help him solve this problem!


The first line contains an integer nn (1 \le n \le 1\,000)(1 \le n \le 1\,000), the number of antennas.

Each of the following nn lines contains integers x_ix_i and y_iy_i (0 \le x_i, y_i \le 10^9)(0 \le x_i, y_i \le 10^9), coordinates of the ii-th antenna.


Output the minimal radius.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-6}10^{-6}.


In test cases worth 50\%50\% points it holds that 1 \le n \le 1001 \le n \le 100.

Sample Input 1

1 1
2 2

Sample Output 1


Sample Input 2

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

Sample Output 2


Explanation for Sample Output 2

Sample Input 3

2020 20
20 2020
2020 2020
20 20

Sample Output 3



There are no comments at the moment.