← 返回题目列表

AtCoder · s8pc_3_e

E. 圆形和许多三角形

中文机器翻译题面 查看原题
最高分数:$850$ 积分

问题陈述

有一个半径为1的圆。
圆的圆周上有 $N$ 个顶点。
顶点在圆周上分成 $N$ 等份。

您可以选择 $3$ 个不同的顶点,并且可以制作一个三角形。
有 $\frac{N(N - 1)(N - 2)}{6}$ 种选择顶点的方法。 问题是:计算 $\frac{N(N-1)(N-2)}{6}$ 个三角形中第 $K$ 个最小三角形的面积。
如果区域相同,可以任意顺序订购。

如果$N = 4,K = 3$,结果如下:
  • 如果选择顶点 $1$、$2$ 和 $3$,则三角形 $= 1$ 的面积。
  • 如果选择顶点 $1$、$2$ 和 $4$,则三角形 $= 1$ 的面积。
  • 如果选择顶点 $1$、$3$ 和 $4$,则三角形 $= 1$ 的面积。
  • 如果选择顶点 $2$、$3$ 和 $4$,则三角形 $= 1$ 的面积。
结果,第三小的三角形的面积 $= 1$。

输入

输入由标准输入按以下格式给出:
$N\K$

输出

  • 请输出第$K$个三角形面积。
  • 打印一个表示答案的浮点数。您答案的相对或绝对误差不应高于 $10^{−9}$。

约束

  • $3 \le N \le 200,000$
  • $1 \le K \le \frac{N(N-1)(N-2)}{6}$

子任务

子任务 1 [ $160$ 点 ]
  • $N \le 100$
子任务 2 [ $240$ 点 ]
  • $N \le 1000$
子任务 3 [ $450$ 点 ]
  • $N \le 200,000$

示例输入 1

4 3

示例输出 1

1.0000000000000
该示例已在问题陈述中进行了解释。

示例输入 2

6 9

示例输出 2

0.86602540378
有 $6$ 种方法可以选择面积为 $\frac{\sqrt{3}}{4}$ 的三角形。
有 $10$ 种方法可以选择面积为 $\frac{\sqrt{3}}{2}$ 的三角形。
有 $2$ 种方法可以选择面积为 $\frac{3 \sqrt{3}}{4}$ 的三角形。
因此,第 9 个最小三角形的面积为 $\frac{\sqrt{3}}{2}$。

示例输入 3

12 220

示例输出 3

1.29903810568
作者:E869120