\(N\) коров (\(1 \leq N \leq 10^5\)) Фермера Джона разместились на его ферме
и хотят построить коммуникационную сеть для обмена электронными текстовыми
сообщениями.
\(i\)-ая корова размещена в точке \((x_i,y_i)\),
где \(0 \leq x_i \leq 10^6\) \(0 \leq y_i \leq 10\).
Стоимость построения коммуникационной линии между коровами \(i\) и \(j\)
есть квадрат расстояния между ними: \((x_i-x_j)^2 + (y_i-y_j)^2\).
Вычислите минимальную стоимость построения коммуникационной сети, так чтобы каждая корова могла разговаривать с любой другой непосредственно или через последовательность линий связи.
**Замечание : Лимитна время на тест = 4s, в дфа раза больше обычного..**
Формат ввода (с клавиатуры / stdin):
Первая строка ввода содержит \(N\), каждая из последующих \(N\) строк описывает
\(x\) и \(y\) - координаты коровы, все числа - целые.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимальную стоимость сети, которая позволит коммуницировать всем
коровам. Заметим, что стоимость может быть очень большой, и может потребовать
64-битную целую типа "long long" в C++.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
|
660
|