J. 贪吃蛇
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

蛇蛇的觅食方式很特殊：

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

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

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

Input

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

对于每组数据：

第一行两个整数 $$$n,k$$$ ($$$1\le k\le n\le 2\times 10^5$$$)，分别表示食物总数和至少需要吃掉的食物数量。

接下来 $$$n$$$ 行，每行两个整数 $$$x_i,y_i$$$ ($$$|x_i|,|y_i|\le 10^6$$$)，表示第 $$$i$$$ 个食物的坐标。保证 $$$(x_i,y_i)\neq(0,0)$$$。

Output

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

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

Example
Input
2
1 1
1 2
3 2
0 2
1 0
-1 -1
Output
0.000000000000
2.356194490192
Note

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

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