EduBrick

Ближайшая пара точек

2500 мс · 256 МБ · всё или ничего

Даны nn различных точек. Найдите квадрат минимального расстояния между двумя из них.

Ответ — целое число: квадрат расстояния между точками с целыми координатами всегда целый. Именно поэтому здесь не нужен ни корень, ни допуск.

Формат ввода

В первой строке nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5). В каждой из следующих nn строк два целых числа (∣x∣,∣y∣≤106|x|, |y| \le 10^6). Все точки различны.

Формат вывода

Выведите одно целое число — квадрат минимального расстояния.

Примеры

ввод
4
0 0
3 4
10 10
0 1
вывод
1
ввод
2
-1000000 -1000000
1000000 1000000
вывод
8000000000000
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.