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 ]
Subtask 2 [ $240$ points ]
Subtask 3 [ $450$ points ]
Sample Output 1
1.0000000000000
This example is already explained in the problem statement.
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 Output 3
1.29903810568
Writer: E869120