题目描述

夏天到了，又到了蛇蛇出来觅食的季节。

蛇蛇生活的地方可以看成一个二维平面，它位于原点 $(0,0)$ 。平面上有 $n$ 个食物，第 $i$ 个食物位于整数坐标 $(x_{i},y_{i})$ ，保证没有食物位于原点。

蛇蛇的觅食方式很特殊：

1. 先选择一个以原点为圆心的角度区间 $[\alpha, \beta]$ ;
2. 以原点为顶点，张开一个以该区间为圆心角的扇形，并且扇形会不断向外扩展，直到将该角度区间内（包含边界）的所有食物全部一口吞下。

扇形的面积大小就是蛇蛇本顿觅食消耗的能量。

蛇蛇现在很饿，它想知道，想要一口吃掉至少 $k$ 个食物，所需的最少能量是多少？

输入格式

第一行一个整数 $t$ ( $1 \leq t \leq 10^4$ ), 表示测试数据组数。保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$ 。
对于每组数据：

• 第一行两个整数 $n, k (1 \leq k \leq n \leq 2 \times 10^{5})$ ，分别表示食物总数和至少需要吃掉的食物数量。
• 接下来 $n$ 行，每行两个整数 $x_{i}, y_{i} \left( |x_{i}|, |y_{i}| \leq 10^{6} \right)$ ，表示第 i 个食物的坐标。保证 $(x_{i}, y_{i}) \neq (0, 0)$ 。

输出格式

对于每组数据，输出一行一个实数，表示最少所需能量。

当你的输出与标准答案的绝对误差或相对误差不超过 $10^{-9}$ 时即被视为正确。

2
1 1
1 2
3 2
0 2
1 0
-1 -1

0.000000000000
2.356194490192

解释

对于第一组数据，只有一个食物且 $k = 1$ ，选择的角度区间恰好只包含该食物的方向，扇形退化为一条从原点出发的线段，面积为 $0$。

对于第二组数据，最优策略为覆盖食物 $(-1, -1)$ 和 $(1, 0)$ ，最少能量是 $\frac{1}{2} \times \frac{3\pi}{4} \times 2 = \frac{3\pi}{4}$ 。