3105 - 最接近点对问题
时间限制 : 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。
来源
分治专题