Полуфинал Республиканской олимпиады Азербайджана 2018-2019
Холодные дни в Динотопии
С угасанием солнечных камней в Динотопии наступили холодные дни. Так, все было ввергнуто во тьму и все живое оказалось на гране гибели. Во избежание этого храбрый Дино вышел на поиски в кромешной тьме. Он нашел два ярких солнечных камня.
Есть надежда на спасение страны! Но надо решить одну проблему. Эти два камня надо расположить в пунктах, находящихся в наиболее близком расстоянии друг от друга. Только в данном случае сияние солнечных камней может достичь солнца и Динотопия будет снова освещена.
В Динотопии находятся n пунктов с солнечными камнями. Эти пункты даны на плоскости с координатами x, y. Помогите храброму Дино найти расстояние между ближайшими двумя пунктами. Как результат надо вывести квадрат этого расстояния.
Примечание: расстояние между двумя точками на плоскости является Эвклидовым.
Input data
В первой строке задано количество пунктов n (1 ≤ n ≤ 10^5). В каждой из следующих n строк указаны два целых числа x[i] и y[i] (-10^8 ≤ x[i], y[i] ≤ 10^8) - координаты точек. Все точки имеют разные координаты.
Output data
Выведите одно целое число – квадрат расстояния между двумя ближайшими пунктами.
Examples
3 1 1 3 1 1 2
1
5 0 0 0 2 2 0 2 2 1 1
2