CFCF2172I.Birthday

提高+/省选-

官方

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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

蛋糕可看作一个以原点 (0,0)(0, 0) 为圆心、半径为 rr 的圆。蛋糕上有 nn 个草莓,第 ii 个草莓的坐标为 (xi,yi)(x_i, y_i)。任意一个草莓到原点的距离都不超过 0.9r0.9r

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

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

输入格式

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

接下来的 nn 行,每行包含两个整数 xix_iyiy_i,表示第 ii 个草莓的坐标。

  • 1n2×1051 \leq n \leq 2 \times 10^5
  • 1r1061 \leq r \leq 10^6
  • xi2+yi20.9r\sqrt{x_i^2 + y_i^2} \leq 0.9r
  • 所有草莓位置互不相同。

输出格式

输出一个实数,表示所有草莓都在同一块的情况下,较小一块蛋糕的最大可能面积。

如果你的答案与标准答案的绝对误差或相对误差不超过 10610^{-6},则视为正确。具体来说,设你的答案为 aa,标准答案为 bb,当 abmax(1,b)106\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
首页