#P1429. 平面最近点对(加强版)
平面最近点对(加强版)
题目背景
P7883 平面最近点对(加强加强版)
题目描述
给定平面上 个点,找出其中的一对点的距离,使得在这 个点的所有点对中,该距离为所有点对中最小的
输入格式
第一行: ,保证 。
接下来 行:每行两个实数: ,表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式
仅一行,一个实数,表示最短距离,精确到小数点后面 位。
3
1 1
1 2
2 2
1.0000
提示
数据保证
P7883 平面最近点对(加强加强版)
给定平面上 n 个点,找出其中的一对点的距离,使得在这 n 个点的所有点对中,该距离为所有点对中最小的
第一行:n ,保证 2≤n≤200000 。
接下来 n 行:每行两个实数:x y ,表示一个点的行坐标和列坐标,中间用一个空格隔开。
仅一行,一个实数,表示最短距离,精确到小数点后面 4 位。
3
1 1
1 2
2 2
1.0000
数据保证 0≤x,y≤109