← 返回题目列表

Codeforces · 2172/I

I. 生日

中文机器翻译题面 查看原题

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 -3
3 -3
-3 3
3 3

输出
复制

11.182380450040

输入
复制

7 15
9 -4
2 -2
8 3
0 4
-6 10
6 6
3 5

输出
复制

353.429173528852

输入
复制

15 15
-4 -1
0 -1
2 -9
0 2
8 1
3 -3
-9 3
8 6
9 7
-9 -1
2 6
-2 7
-10 -8
4 0
-5 -8

输出
复制

168.906562205067