問題一覧 > 通常問題

No.2873 Kendall's Tau

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が10610^{-6} 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 78
作問者 : 寝癖寝癖 / テスター : yuusaanyuusaan 👑 seekworserseekworser
1 ProblemId : 11163 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-17 23:44:48

問題文

NN 個のデータ (x1,y1),,(xN,yN)(x_1,y_1),\cdots,(x_N,y_N) が与えられるので、ケンドールの順位相関係数を求めてください。

ただし、ケンドールの順位相関係数 τ\tau は以下のように定義されます。 τ=PQR×S\tau=\frac{P-Q}{\sqrt{R\times S}}

  • PP: 異なる添字の組 (i,j) (1i<jN)(i, j)\ (1\le i < j\le N) であって、(xixj)(yiyj)>0(x_i-x_j)(y_i-y_j)> 0 となるようなものの個数
  • QQ: 異なる添字の組 (i,j) (1i<jN)(i, j)\ (1\le i < j\le N) であって、(xixj)(yiyj)<0(x_i-x_j)(y_i-y_j)< 0 となるようなものの個数
  • RR: 異なる添字の組 (i,j) (1i<jN)(i, j)\ (1\le i < j\le N) であって、xixjx_i\neq x_j となるようなものの個数
  • SS: 異なる添字の組 (i,j) (1i<jN)(i, j)\ (1\le i < j\le N) であって、yiyjy_i\neq y_j となるようなものの個数

なお、本問題の制約上、R×S0R\times S\neq0 となることが保証されます。

入力

NN
x1 y1x_1\ y_1
\vdots
xN yNx_N\ y_N
  • 2N2×1052\le N\le 2\times10^5
  • すべての ii に対して xi,yi109|x_i|,|y_i|\le10^9
  • 異なる添字の組 (i,j)(i,j) が存在して xixjx_i\neq x_j
  • 異なる添字の組 (i,j)(i,j) が存在して yiyjy_i\neq y_j
  • 入力はすべて整数

出力

ケンドールの順位相関係数を一行で出力してください。

なお、想定解答との絶対誤差または相対誤差が 10610^{-6} 以下であれば正解と判定されます。

サンプル

サンプル1
入力
3
1 4
1 5
9 2
出力
-0.8164965809277260

ケンドールの順位相関係数の定義における P,Q,R,SP,Q,R,S の値は以下のとおりです。

  • 条件に該当する組が存在しないため P=0P=0
  • (1,3),(2,3)(1,3),(2,3) が条件に該当するため Q=2Q=2
  • (1,3),(2,3)(1,3),(2,3) が条件に該当するため R=2R=2
  • (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) が条件に該当するため S=3S=3

したがって、求める値は 022×3=26=0.816496...\frac{0-2}{\sqrt{2\times3}}=-\frac{2}{\sqrt{6}}=0.816496... となります。

サンプル2
入力
2
1 1
2 2
出力
1.0000000000000000

サンプル3
入力
5
4 4
5 7
0 4
2 10
-6 4
出力
0.3585685828003181

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