CFCF2172I.Birthday
提高+/省选-
官方
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Anon 和 Soyo 是好朋友。为了庆祝 Anon 的生日,Soyo 决定买一个蛋糕。经过精心挑选,她选了一个圆形草莓蛋糕,在家和 Anon 一起分享。
蛋糕可看作一个以原点 (0,0) 为圆心、半径为 r 的圆。蛋糕上有 n 个草莓,第 i 个草莓的坐标为 (xi,yi)。任意一个草莓到原点的距离都不超过 0.9r。
Soyo 想用一条直线把蛋糕切成两块。由于 Anon 特别喜欢草莓,所以 Soyo 想让 Anon 吃到包含所有草莓的一块。如果某个草莓恰好在切割线上,Soyo 可以将其归入任意一块。
Soyo 希望较小的那块蛋糕尽可能大。请你帮 Soyo 计算出,所有草莓都在同一块的情况下,切割后较小一块蛋糕的最大可能面积。
输入格式
第一行包含两个整数 n 和 r,分别表示蛋糕上的草莓数量和蛋糕的半径。
接下来的 n 行,每行包含两个整数 xi 和 yi,表示第 i 个草莓的坐标。
- 1≤n≤2×105
- 1≤r≤106
- xi2+yi2≤0.9r
- 所有草莓位置互不相同。
输出格式
输出一个实数,表示所有草莓都在同一块的情况下,较小一块蛋糕的最大可能面积。
如果你的答案与标准答案的绝对误差或相对误差不超过 10−6,则视为正确。具体来说,设你的答案为 a,标准答案为 b,当 max(1,∣b∣)∣a−b∣≤10−6 时,答案正确。
输入输出样例
输入#1
4 5 -3 -3 3 -3 -3 3 3 3
输出#1
11.182380450040