Distance Between the Closest Pair of Points

Time limit1sMemory limit256 MB

Summary

Given up to 500,000 distinct points, find the two closest and print the square of their distance.

Level: Medium7 of 10
Topics: Divide and conquer, Sorting, Geometry, Binary search
Solved: No attempts yet

Problem

There are $n$ points $P_1, P_2, \dots, P_n$ on a plane. Among these points, find the two that are closest to each other and determine the distance between them.

Input

The first line contains the number of points $n$ .

Each of the next lines, from the 2nd line through the $(n+1)$ -th line, contains the coordinates $x$ and $y$ of a single point separated by a space. The values on the $(i+1)$ -th line are the $x$ - and $y$ -coordinates of point $P_i$ .

Constraints: $2 \le n \le 500000$ and $-10000 \le x, y \le 10000$ . All points have distinct coordinates (no two points share the same coordinates).

Output

Print the square of the distance between the closest pair of points.

Examples2

Example 1
Input
```
3
5 5
0 0
-3 -4
```
Expected output
```
25
```
Example 2
Input
```
2
0 0
1 1
```
Expected output
```
2
```