Cold Days in Dinotopia
As the sunstones in Dinotopia begin to fade, cold days have descended upon the land. Darkness envelops everything, threatening all life with extinction. To avert this disaster, the courageous Dino ventures into the pitch-black night and discovers two radiant sunstones.
There is a glimmer of hope for Dinotopia's salvation! However, a challenge remains: these two stones must be placed at the points closest to each other. Only then can the sunstones' light reach the sun, restoring illumination to Dinotopia.
In Dinotopia, there are n points where sunstones are located. These points are represented on a plane with coordinates x and y. Your task is to assist the brave Dino in finding the distance between the two closest points. You need to output the square of this distance.
Note: The distance between two points on a plane is measured using the Euclidean method.
Input
The first line contains the number of points n (1 ≤ n ≤ 10^5). Each of the following n lines contains two integers x[i] and y[i] (-10^8 ≤ x[i], y[i] ≤ 10^8) - the coordinates of the points. All points have unique coordinates.
Output
Output a single integer – the square of the distance between the two closest points.