Anon 和 Soyo 是好朋友。为了庆祝阿农的生日,索约决定买一个蛋糕。经过仔细挑选,她选择了一个圆形的草莓蛋糕与阿农在家分享。
蛋糕被建模为一个以原点 $$$(0, 0)$$$ 为中心、半径为 $$$r$$$ 的圆。蛋糕上有$$$n$$$个草莓,其中第$$$i$$$个草莓位于$$$(x_i, y_i)$$$处。任意草莓距原点的距离最多为$$$0.9r$$$。
Soyo 想要用一条直线将蛋糕切成两块。由于 Anon 喜欢草莓,Soyo 希望 Anon 的作品包含所有草莓。如果草莓位于切割线上,Soyo 可以将其分配给任意一块。
Soyo 希望将较小的部分做得尽可能大。鉴于所有草莓都位于同一块上,请帮助 Soyo 确定较小块的最大可能面积。
输入
第一行包含两个整数$$$n$$$和$$$r$$$,分别代表蛋糕上草莓的数量和蛋糕的半径。
以下$$$n$$$行中的第$$$i$$$行包含两个整数$$$x_i$$$和$$$y_i$$$,代表第$$$i$$$个草莓的坐标。
- $$$1 \leq n \leq 2 \times 10^5$$$
- $$$1 \leq r \leq 10^6$$$
- $$$\sqrt{{x_i}^2 + {y_i}^2} \leq 0.9r$$$
- 所有草莓都处于不同的点。
输出
在一行中打印一个实数,代表较小部分的最大可能面积,假设所有草莓都位于同一块上。
如果绝对或相对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$${\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}}$$$,则认为您的答案是正确的。
示例
输入复制
4 5-3 -33 -3-3 33 3
输出复制
11.182380450040
输入复制
7 159 -42 -28 30 4-6 106 63 5
输出复制
353.429173528852
输入复制
15 15-4 -10 -12 -90 28 13 -3-9 38 69 7-9 -12 6-2 7-10 -84 0-5 -8
输出复制
168.906562205067