UOJ Logo Zijian Online Judge

ZOJ

#54. 观察星象

统计

EI 在用望远镜观察星星,星空中共有 $n$ 个星星,每个星星观察起来有一个二维直角坐标 $(x, y)$。他的望远镜如果定位在 $(x_0, y_0)$ 处,可以看到 $(x - x_0)^2 + (y - y_0)^2 \le r^2$ 的星星,望远镜的大小 $r$ 是可以调整的,EI 想知道如果他想要至少看到 $m$ 个星星,至少需要把 $r$ 设置到多大?

输入格式

第一行输入两个正整数 $n,m$,表示星星的数量和要求看到的星星数量。

接下来 $m$ 行每行两个整数 $x, y$,表示一个星星的坐标。保证没有两个星星坐标相同。

输出格式

输出一行一个正实数,表示望远镜最小的半径。令你的答案为 $a$,标准答案为 $b$,如果满足 $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$(即绝对误差或者相对误差不超过 $10^{-6}$)即为正确。

样例一

input

4 3
0 0
1 1
2 3
3 3

output

1.41421356

explanation

这是 $\sqrt 2$。

限制与约定

对于 $100\%$ 的数据,保证 $2\le m\le n\le 2000, |x|, |y| \le 10^4$。

子任务编号 $n$ $m$ 分值
$1$ $\le 50$ $\le n$ $10$
$2$ $\le 200$ $15$
$3$ $\le 700$ $15$
$4$ $\le 2000$ $= n$ $20$
$5$ $\le n$ $40$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载