Background

  最近点对问题是计算几何中的经典难题：在平面上给定 $n$ 个点，要求找出距离最近的一对点。朴素算法需要检查所有点对，时间复杂度为 $O(n^2)$；而分治算法能够将复杂度降低到 $O(n \log n)$，充分体现了“分解—递归—合并”范式在提升算法效率方面的威力。

  通过本题，学生将掌握如何在几何问题中运用分治策略，理解带状区域剪枝的核心思想，并体会在算法设计中维护辅助数据结构以及避免精度误差和溢出的重要性。

Description

  给定 $n$ 个二维点 $(x_i, y_i)$，请找出任意两点间的最小欧氏距离。为避免浮点误差，建议输出距离的平方值。

输入格式

  第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）。

  接下来 $n$ 行，每行包含两个整数 $x_i, y_i$（$|x_i|, |y_i| \leq 10^9$）。

输出格式

  输出最近点对的距离平方，使用 64 位整数表示。

样例 #1

样例输入 #1

5
0 0
1 1
2 2
5 1
3 3

样例输出 #1

2

  最近点对为 $(0, 0)$ 与 $(1, 1)$，距离平方为 $1^2 + 1^2 = 2$。