CBOJ Exec Selection Contest Problem 1 - Networking

Points: 12 (partial)
Time limit: 1.0s
Java 4.0s
Python 4.0s
Memory limit: 512M

Problem type

Bob is doing a little bit of networking!

Bob needs to connect $$N$$ stations that are scattered across the city, which can be represented as points on a 2D plane. He will set the transmission radius of each station to be the same nonnegative real number $$R$$. The range of a station is defined as the set of all points whose euclidean distance to the station is at most $$R$$. If the ranges of two stations share a common point, those stations will be able to directly communicate with each other.

Additionally, if stations $$A$$ and $$B$$ can communicate as well as stations $$B$$ and $$C$$, then stations $$A$$ and $$C$$ can also communicate through station $$B$$.

Bob wants to make all $$N$$ stations to be able to communicate with each other. But with a limited budget, Bob will need to choose the smallest possible radius $$R$$! Can you help Bob figure it out?

For this problem, Python users should submit their submissions in PyPy over CPython.

Input Specification

The first line contains an integer $$N$$ $$(1 \le N \le 1\,000)$$, representing the number of stations.

Each of the following $$N$$ lines contains two integers $$x_i$$ and $$y_i$$ $$(0 \le x_i, y_i \le 10^9)$$, representing the coordinates of the $$i$$-th station.

Output Specification

Output a decimal $$R$$, representing the minimal radius. Your answer will be considered correct if its absolute or relative error doesn't exceed $$10^{-6}$$.

Note that you will be required to pass the sample input to receive points for the subtasks. However, you will not be required to pass subtask 1 in order to get points on subtask 2.

$$1 \le N \le 4$$

Sample Input 1

4
2020 20
20 2020
2020 2020
20 20

Sample Output 1

1000.0000000