Closest Pair of Points

Time limit1sMemory limit256 MB

Summary

Given up to 100,000 points, compute the minimum squared distance between any two points efficiently.

Level: Medium6 of 10
Topics: Divide and conquer, Sorting, Geometry
Solved: No attempts yet

Problem

Given n points on a two-dimensional plane, write a program that finds the squared distance between the closest pair of points.

Input

The first line contains a natural number n (2 <= n <= 100,000). Each of the next n lines contains the x and y coordinates of one point. Every coordinate is an integer whose absolute value is at most 10,000. Multiple points may have exactly the same coordinates.

Output

Print the squared distance between the closest pair of points.

Examples1

Example 1
Input
```
4
0 0
10 10
0 10
10 0
```
Expected output
```
100
```