問題一覧 > 通常問題

No.1385 Simple Geometry 2

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : Mitarushi / テスター : cardano1016 蜜蜂
お気に入りにしたユーザー ProblemId : 5870 / 自分の提出
問題文最終更新日: 2021-03-23 18:36:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘高入試コンテスト2021 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。