3105 - 最接近点对问题

通过次数

165

提交次数

595

时间限制 : 1 秒
内存限制 : 128 MB

二维平面上的n个点,不存在完全重叠的两个点。请找出最接近的两个点之间的距离。

输入

第一行为一个正整数n。 第二行为n个数,表示n个点的横坐标。 第三行为n个数,表示n个点的纵坐标。

输出

最接近的两个点的欧式距离(保留四位有效小数)

样例

输入

6
13.43 37.40 78.76 91.64 90.46 57.83
10.76 75.48 99.56 38.22 8.07 20.02

输出

30.1731

提示

样例1中,最接近的点对为(90.46,8.07)和(91.64,38.22),距离为30.1731。 对于30%的数据,n\le 1000, 对于100%的数据,n\le 50000,坐标值均\le 100000

来源

分治专题