题目描述

Hana 最近需要生产一款雷达，用于监测她管理的群岛的异常情况。

海洋上有 $n$ 座岛屿，第 $i$ 座岛屿位于坐标 $(x_i,y_i)$ ，可以被当作平面上的一个点。假设雷达的扫描角度范围为 $α$ ，当雷达旋转到角度 $θ$ 时，它可以监测到所有位于 $[\theta-\frac{\alpha}{2},\theta+\frac{\alpha}{2}]$ 角度内的岛屿。

Hana 最近手头紧张，因此她希望最小化建造雷达的费用。她想知道，当雷达被放置在坐标原点 ($0,0$)
时，雷达的扫描角度范围 $α$ 最小应该是多少，才能保证雷达在旋转到任意角度 $θ$ 时，都能监测到至少 $k$ 个岛屿。

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$（$1≤T≤10^4$）。每组测试数据的格式如下。

每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1≤k≤n≤2×10^5$），表示岛屿的总数量和雷达至少要监测到的岛屿的数量。

接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$\left|x_i\right|,\left|y_i\right|≤10^9$），表示一座岛屿的位置。保证任意两个岛屿的坐标互不相同，且不位于原点。

在每个测试文件内，保证所有测试数据的 $n$ 之和不超过 $2×10^5$。

输出格式

对于每组数据，输出一行一个小数，表示雷达扫描角度范围的最小值，以弧度制形式输出。

当你的输出与标准答案的绝对误差或相对误差不超 $10^{-6}$ 时，你的输出将会被判定为正确。

具体地说，令你的答案为 $a$ ，标准答案为 $b$ 。你的答案被认为是正确的当且仅当 $\frac{\left|a-b\right|}{max{(1,\left|b\right|)}}\le10^{-6}$ 。

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

6.2831853072
1.5707963268
5.4977871438
3.1415926546
3.1415926536

解释 #1

对于样例的第一组测试数据，平面上只有一座岛屿（$0,1$）。要保证时刻都能监测到至少一座岛屿，必须将雷达的监测范围设置成 $360°$ ，在弧度制下即为 $2π$。

对于样例的第二组测试数据，平面上有 $8$ 座岛屿，任意两座岛屿相隔 $45°$ 。若雷达的范围小于 $90°$ ，
当雷达的一个边界刚好不能照射到一座岛屿时，雷达只能监测到一座岛屿（如示意图中左侧的情况)。因此，雷达监测范围的最小值是 $90°$ ，这能保证任意时刻都能监测到至少两座岛屿。

题目来源

2024-ICPC国际大学生程序设计竞赛-昆明站 - H题