测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A16610. Birthday

编程题 提高+/省选-
知识点

题目描述

Anon 和 Soyo 是好朋友。为了庆祝 Anon 的生日,Soyo 决定买一个蛋糕。经过精心挑选,她选了一个圆形草莓蛋糕,在家和 Anon 一起分享。

蛋糕可看作一个以原点 $(0, 0)$ 为圆心、半径为 $r$ 的圆。蛋糕上有 $n$ 个草莓,第 $i$ 个草莓的坐标为 $(x_i, y_i)$。任意一个草莓到原点的距离都不超过 $0.9r$。

Soyo 想用一条直线把蛋糕切成两块。由于 Anon 特别喜欢草莓,所以 Soyo 想让 Anon 吃到包含所有草莓的一块。如果某个草莓恰好在切割线上,Soyo 可以将其归入任意一块。

Soyo 希望较小的那块蛋糕尽可能大。请你帮 Soyo 计算出,所有草莓都在同一块的情况下,切割后较小一块蛋糕的最大可能面积。

输入格式

第一行包含两个整数 $n$ 和 $r$,分别表示蛋糕上的草莓数量和蛋糕的半径。

接下来的 $n$ 行,每行包含两个整数 $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| a - b \right|}{\max(1, \left| b \right|)} \leq 10^{-6}$ 时,答案正确。

输入输出样例

输入 #1
4 5
-3 -3
3 -3
-3 3
3 3
输出 #1
11.182380450040
上一题 去做题 下一题