E - Circle and Many Triangles Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Max Score: $850$ Points

Problem statement

There is a circle which radius is 1.
There are $N$ vertices on the circle's circumference.
The vertices divides into $N$ equal parts over the circumference.

You can choose $3$ distinct vertices, and you can make a triangle.
There are $\frac{N(N - 1)(N - 2)}{6}$ ways choosing vertices. The question is: Calculate the area of $K$-th smallest triangle in $\frac{N(N-1)(N-2)}{6}$ triangles.
If the area is same, you can order in any order.

If $N = 4, K = 3$, the result is following:
  • If you select vertices $1$, $2$, and $3$, the area of triangle $= 1$.
  • If you select vertices $1$, $2$, and $4$, the area of triangle $= 1$.
  • If you select vertices $1$, $3$, and $4$, the area of triangle $= 1$.
  • If you select vertices $2$, $3$, and $4$, the area of triangle $= 1$.
As a result, the 3rd smallest triangle's area $= 1$.

Input

The input is given from Standard Input in the following format:
$N \ K$

Output

  • Please output the $K$-th triangle area.
  • Print a floating number denoting the answer. The relative or absolute error of your answer should not be higher than $10^{−9}$.

Constraints

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

Subtasks

Subtask 1 [ $160$ points ]
  • $N \le 100$
Subtask 2 [ $240$ points ]
  • $N \le 1000$
Subtask 3 [ $450$ points ]
  • $N \le 200,000$

Sample Input 1

4 3

Sample Output 1

1.0000000000000
This example is already explained in the problem statement.

Sample Input 2

6 9

Sample Output 2

0.86602540378
There are $6$ ways to choose a triangle which area is $\frac{\sqrt{3}}{4}$.
There are $10$ ways to choose a triangle which area is $\frac{\sqrt{3}}{2}$.
There are $2$ ways to choose a triangle which area is $\frac{3 \sqrt{3}}{4}$.
Therefore, the 9th smallest triangle's area is $\frac{\sqrt{3}}{2}$.

Sample Input 3

12 220

Sample Output 3

1.29903810568
Writer: E869120
配点： $850$ 点

問題文

半径が $1$ の円があり、頂点 $1$ ～ $N$ が時計回りに並んでいます。
頂点は, 円周を $N$ 等分しています。
square1001は, $3$ つの頂点を選んで三角形を作ろうとしています。

$\frac{N(N-1)(N-2)}{6}$ 通りの作り方のうち, 面積が小さい順に数えて $K$ 番目となる三角形の面積を出力してください。
ただし, 面積が同じ場合は、面積だけを出力すればいいので順番は適当で構いません。

例えば, $N = 4, K = 3$ のとき, 次のようになります。
  • 3頂点の番号が $(1,2,3)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(1,2,4)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(1,3,4)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(2,3,4)$ のとき, 面積 $= 1$
よって, 3番目の三角形の面積 $= 1.0$ となります。

入力

入力は以下の形式で標準入力から与えられる。
$N \ K$
  • 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$点 ]
  • 追加の制約はない。

入力例1

4 3

出力例1

1.000000000000000000
この入力例は問題文で説明したとおりです。

入力例2

6 9

出力例2

0.86602540378
$N = 6$ のとき, 面積が $\frac{\sqrt{3}}{4}$ となるような頂点の選び方は $6$ 通り, 面積が $\frac{\sqrt{3}}{2}$ となるような頂点の選び方は $12$ 通り, 面積が $\frac{3 \sqrt{3}}{4}$ となるような頂点の選び方は $2$ 通りあります。
よって, $K = 9$ 番目の三角形の面積は $\frac{\sqrt{3}}{2}$ となります。

入力例3

12 220

出力例3

1.29903810568
$N = 12$ のとき, 三角形の作り方は $\frac{12 \times 11 \times 10}{6} = 220$ 通りあります。
この中で面積が一番大きいのは正三角形となるときなので, $K = 220$ 番目の三角形の面積は $\frac{3 \sqrt{3}}{4}$ となります。
問題作成者：E869120