P10825 [EC Final 2020] Circle

庞教授研究最小覆盖圆问题。他不喜欢随机算法，所以决定寻找一个高效的确定性算法。他从经典的二分查找思想开始。在每次二分查找的迭代中，需要解决以下问题： 给定一个圆的半径 $r$ 和一个凸包 $C$，定义 $S$ 为 $$S=\{p\ |\ \text{以 $p$ 为圆心，半径为 $r$ 的圆覆盖 $C$ 的所有点}\}.$$ 求 $S$ 的面积。

第一行包含一个正整数 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n$ 和 $r$ ($1\le n\le 1000$, $1\le r\le 30000$)，用一个空格分隔，表示凸包的顶点数和半径。如果 $n=1$，则凸包仅包含 1 个点。如果 $n=2$，则凸包为一条线段。 接下来的 $n$ 行中的每一行包含两个整数 $x, y$ ($-10000\le x, y\le 10000$)，用一个空格分隔，表示一个顶点的坐标 $(x, y)$。保证没有两个顶点重合，且没有三个顶点共线。顶点按逆时针顺序列出。 保证所有测试用例中 $n$ 的总和不超过 $200000$。

输出一个小数表示答案。如果绝对误差或相对误差不超过 $10^{-6}$，则你的答案将被视为正确。

（由 ChatGPT 4o 翻译）