CBOJ Exec Selection Contest Problem 1 - Networking

Submit solution

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.

Subtask 1 [10%]

\(1 \le N \le 4\)

Subtask 2 [15%]

The answer is an integer.

Subtask 3 [75%]

No additional constraints.

Sample Input 1

2020 20
20 2020
2020 2020
20 20

Sample Output 1



There are no comments at the moment.