题目名称 1159. 平面上的最接近点对
输入输出 nearest.in/out
难度等级 ★★★
时间限制 3000 ms (3 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatar王者自由 于2012-10-16加入
开放分组 全部用户
提交状态
分类标签
排序 分治
分享题解
通过:57, 提交:195, 通过率:29.23%
GravatarMagic_Sheep 100 0.053 s 0.74 MiB C++
Gravatarxjzsq 100 0.076 s 9.45 MiB C++
Gravatarxjzsq 100 0.078 s 9.45 MiB C++
GravatarOI永别 100 0.081 s 2.15 MiB C++
Gravatarevd 100 0.082 s 2.15 MiB C++
GravatarOI永别 100 0.083 s 2.15 MiB C++
GravatarSatoshi 100 0.086 s 0.77 MiB C++
GravatarOI永别 100 0.086 s 2.15 MiB C++
GravatarBenjamin 100 0.089 s 6.07 MiB C++
Gravatarrewine 100 0.090 s 6.42 MiB C++
关于 平面上的最接近点对 的近10条评论(全部评论)
魔鬼题目留名
GravatarTheresis
2019-07-03 11:00 7楼
小数据暴力出奇迹。
大数据随机化算法乱搞压正解。
Gravatarsxysxy
2017-04-03 22:39 6楼
套用自己的几何模板的感觉就是好
Gravatar_Itachi
2016-09-11 15:17 5楼
Gravatar农场主
2015-10-08 22:20 4楼
分治大法好!
GravatarSatoshi
2015-09-16 08:28 3楼
小cheat...
GravatarOI永别
2014-05-13 16:38 2楼
我水啊....
GravatarQhelDIV
2012-10-25 21:51 1楼

1159. 平面上的最接近点对

★★★   输入文件:nearest.in   输出文件:nearest.out   简单对比
时间限制:3 s   内存限制:512 MiB

【问题描述】

给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。

【输入格式】

第一行:n;2≤n≤60000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

【输出格式】

仅一行,一个实数,表示最短距离,精确到小数点后面4位。

【输入样例】

3
1 1
1 2
2 2

【输出样例】

1.0000