No.1385 Simple Geometry 2
タグ : / 解いたユーザー数 21
作問者 :
cardano1016
蜜蜂
Problem Statement
You are given $\ N\ $ points on the circumference of the unit circle centered at the point $\ (0,0)\ $ in the $xy\ $ plane.
The coordinates of the $i\ $-th point are $\ \left(\cos\frac{2 \pi T_i} {L}, \sin \frac{2 \pi T_i} {L}\right)\ $. $\ (1 \leq i \leq N)$
When $\ 3\ $ distinct points are chosen uniformly at random from these $\ N\ $ points, find the expected value of the area of the triangle formed by connecting the chosen $\ 3\ $ points.
Input
$N\ \ L$ $T_1\ \ T_2\ \ldots\ T_N$
- $3 \leq N \leq 5 \times 10^5$
- $N \leq L \leq 10^{12}$
- $0 \leq T_i \leq L-1 (1 \leq i \leq N)$
- $T_i < T_{i+1} (1 \leq i \leq N-1)$
- All inputs are integers.
Output
Output the expected value of the area, followed by a newline.
Your answer is judged as correct if its absolute or relative error from the expected solution is at most $\ 10^{-9}\ $.
Sample
Sample 1
Input
3 4
0 1 3
Output
1.000000000000000
The coordinates of the $3\ $ points are $\ (1,0),(0,1),(0,-1)\ $, and the area of the triangle formed by connecting these $\ 3\ $ points is $1$.
Sample 2
Input
4 8
1 3 5 6
Output
0.853553390593274
Sample 3
Input
10 100
2 11 35 42 54 69 89 91 93 99
Output
0.499839007828336
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。