在真空中,一块无限平坦光滑绝缘不导热草地上有很多光滑且相同球形竹鼠,它们的坐标为(xi,yi)。竹鼠之间会通过脑电波联系彼此。现在请问相距最近两只竹鼠的直线距离分别是多少(所有竹鼠都在草地的第一象限)?
格式
输入格式:
第一行一个整数n;
接下来 n行每行两个非负浮点数,xi,yi,表示第 i个点的 X 坐标与 Y 坐标。xi,yi都精确到小数点后两位。
输出格式:
一行,一个浮点数,最短距离。精确到小数点后4位。
样例 1
输入:
4
0.0 0.0
0.0 1.0
1.0 0.0
1.0 1.0
输出:
1.0000
备注
其中: 0≤n≤10^5,竹鼠的坐标数据范围在int型范围内。并且可能会有重叠的竹鼠。
思路:模板题,最近点对问题,用分治解决。
即将区域分成 l----mid---r,即最短距离有三种情况:全在左边、全在右边、一个在左一个在右