解题思路

核心做法（分治 + 归并按 y 排序）：

1. 先按 x 坐标排序所有点。
2. 递归把点集分成左右两半，分别求出左右内部的最小距离平方 d。
3. 在合并阶段，把当前区间按 y 坐标归并排序（保证递归返回后区间内点按 y 有序）。
4. 只需检查“中线附近”宽度为 sqrt(d) 的条带（strip）：满足 (x-midx)^2 < d 的点。
5. 条带内点按 y 有序后，对每个点只需向后检查 y 差平方小于 d 的少量点（理论保证常数个），更新最小值。

题目内容

某城市计划在多个地点建立信号塔，所有信号塔的覆盖范围均为圆形，现给定所有信号塔的坐标(二维平面上的点)，要求检测信号塔间的距离 $(x_1-x_2 )^2+(y_1- y_2)^2$，请返回所有信号塔间的最小距离。

输入描述

第一行为整数 $n(2≤n≤100000)$，表示表示信号塔数量。

接下来 $n$ 行，每行包含两个整数 $x(-100000≤x≤100000)$ 和 $y(-100000≤y≤100000)$，以空格分隔，表示信号塔的坐标。

输出描述

一个整数，表示所有信号塔间的最小距离。

样例1

输入

5
0 0
0 5
3 4
3 5
3 6

输出

1

说明

最近的点对是 $(3,4)$ 和 $(3,5)$，距离为 $(3-3)^2+(5-4)^2=1$ 。

样例2

输入

4
0 0
0 1
1 0
1 1

输出

1

说明

最近的点对是 $(0,0)、(0,1)$ 和 $(0,0)、(1,0)$，距离为 $(0-0)^2+ (1-0)^2=1$

样例3

输入

2
0 0
1 1

输出

2

说明

最近的两个点是 $(0,0)$ 和 $(1,1)$，距离为 $(1-0)^2+(1-0)^2=2$ 。