問題一覧 > 通常問題

No.1385 Simple Geometry 2

レベル : / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 17
作問者 : MitarushiMitarushi / テスター : cardano1016cardano1016 蜜蜂蜜蜂
2 ProblemId : 5870 / 出題時の順位表
問題文最終更新日: 2021-03-23 18:36:27

問題文

$xy\ $平面上の点$\ (0,0)\ $を中心とする単位円の円周上にある$\ N\ $個の点が与えられます。
$i\ $番目の点の座標は$\ \left(\cos\frac{2 \pi T_i} {L}, \sin \frac{2 \pi T_i} {L}\right)\ $です。$\ (1 \leq i \leq N)$

これら$\ N\ $個の点の中から相異なる$\ 3\ $点を一様ランダムに選ぶとき、選んだ$\ 3\ $点を結んでできる三角形の面積の期待値を求めてください。

入力

$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)$
  • 入力はすべて整数

出力

面積の期待値を出力して、最後に改行してください。
なお、想定解との絶対誤差あるいは相対誤差が$\ 10^{-9}\ $以下の時、正答と判定されます。

サンプル

サンプル1
入力
3 4
0 1 3
出力
1.000000000000000

$3\ $点の座標は$\ (1,0),(0,1),(0,-1)\ $であり、この$\ 3\ $点を結んでできる三角形の面積は$1$です。

サンプル2
入力
4 8
1 3 5 6
出力
0.853553390593274

サンプル3
入力
10 100
2 11 35 42 54 69 89 91 93 99
出力
0.499839007828336

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。