e-olymp
Competitions

Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020

Холодные дни в Динотопии

С угасанием солнечных камней в Динотопии наступили холодные дни. Так, все было ввергнуто во тьму и все живое оказалось на гране гибели. Во избежание этого храбрый Дино вышел на поиски в кромешной тьме. Он нашел два ярких солнечных камня. Есть надежда на спасение страны! Но надо решить одну проблему. Эти два камня надо расположить в пунктах, находящихся в наиболее близком расстоянии друг от друга. Только в данном случае сияние солнечных камней может достичь солнца и Динотопия будет снова освещена. В Динотопии находятся n пунктов с солнечными камнями. Эти пункты даны на плоскости с координатами x, y. Помогите храброму Дино найти расстояние между ближайшими двумя пунктами. Как результат надо вывести квадрат этого расстояния.

Примечание: Здесь расстояние между двумя координатами на плоскости является расстоянием эвклида между ними.

Входные данные

В первой строке указано целое число n, обозначающее количество пунктов, в каждой из следующих n строк указаны два целых числа xi и yi , обозначающие координаты пунктов. Все пункты имеют в разные координаты.

Выходные данные

Выведите одно целое число – определите квадрат расстояния между двумя ближайшими пунктами.

Ограничения

  • 1 ≤ n ≤ 105
  • -108 ≤ xi, yi ≤ 108
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
1 1
3 1
1 2
Output example #1
1
Input example #2
5
0 0
0 2
2 0
2 2
1 1
Output example #2
2