← 返回 citadel 的题目列表Closest Pair of Points in a 2D Plane
类型：online_judge
Given n points in a two-dimensional plane, find the minimum Euclidean distance between any pair of distinct points.
To avoid floating-point precision issues, output the squared minimum Euclidean distance:
(x1 - x2)^2 + (y1 - y2)^2
If multiple pairs have the same minimum distance, output only that minimum squared distance.
Your algorithm must run in O(n log n) total time. An O(n^2) all-pairs solution is not acceptable.
Input Format
First line: an integer n
Next n lines: two integers x y, representing one point.
Output Format
Print one integer: the minimum squared Euclidean distance between any two points.
Constraints
2 <= n <= 200,000
-10^9 <= x, y <= 10^9
Coordinates may be duplicated. If duplicate points exist, the answer is 0.
Example 1
Input:
4
0 0
3 4
1 1
10 10
Output:
2
Explanation: points (0, 0) and (1, 1) have squared distance 2.
Example 2
Input:
3
1 2
1 2
5 6
Output:
0
Example
Input
4
0 0
3 4
1 1
10 10
Output
2