\(N\) (\(1 \leq N \leq 1000\)) коров Фермера Джона хотят организовать безопасную
систему для передачи важных сообщений.
Они купили по одной "воки-токи" для каждой коровы. Каждая такая "воки-токи"
имеет ограниченный радиус передачи информации. Но коровы могут передавать
сообщения "по эстафете", поэтому нет необходимости для каждой коровы иметь
возможность передавать сообщения непосредственно любой другой корове.
Коровам нужно решить сколько денег необходимо потратить на "воки-токи".
Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние
до \(\sqrt{X}\). То есть, квадрат расстояния между коровами стоит не более \(X\)
чтобы обеспечить их коммуникацией.
Помогите коровам определить минимальное целое \(X\) такое, что сообщение от любой
коровы сможет достичь любой другой коровы.
ФОРМАТ ВВОДА (файл moocast.in):
Первая строка ввода содержит
\(N\).
Каждая из \(N\) последующих строк содержит \(x\) и \(y\) координаты одной коровы.
И то и другое - целое в интервале \(0 \ldots 25,000\).
ФОРМАТ ВЫВОДА (файл moocast.out):
Напишите в одну строку целое \(X\) - минимальное количество денег, которое
коровы должны потратить на "воки-токи"
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3
5 4
7 2
6 1
|
17
|