A16610 · Birthday · GESP考级

题目描述

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

输出 #1

11.182380450040