/* -*- coding: utf-8 -*- * * 2873.cc: No.2873 Kendall's Tau - yukicoder */ #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; /* typedef */ using ll = long long; using pii = pair; template struct BIT { int n; vector bits; BIT() {} BIT(int _n) { init(_n); } void init(int _n) { n = _n; bits.assign(n + 1, 0); } T sum(int x) { x = min(x, n); T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { if (x <= 0) return; while (x <= n) { bits[x] += v; x += (x & -x); } } }; /* global variables */ int xs[MAX_N], ys[MAX_N], uys[MAX_N]; pii xys[MAX_N]; BIT bit; /* subroutines */ ll calcr(int n, int xs[]) { sort(xs, xs + n); ll r = 0; for (int i = 0; i < n;) { int j = i; while (i < n && xs[j] == xs[i]) i++; r += (ll)(n - (i - j)) * (i - j); } return r / 2; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); copy(ys, ys + n, uys); sort(uys, uys + n); int m = unique(uys, uys + n) - uys; for (int i = 0; i < n; i++) ys[i] = lower_bound(uys, uys + m, ys[i]) - uys; for (int i = 0; i < n; i++) xys[i] = {xs[i], ys[i]}; sort(xys, xys + n); bit.init(m); ll p = 0, q = 0; for (int i = 0; i < n;) { int j = i; while (i < n && xys[j].first == xys[i].first) { auto [xi, yi] = xys[i++]; p += bit.sum(yi); q += j - bit.sum(yi + 1); } while (j < i) { auto [xj, yj] = xys[j++]; bit.add(yj + 1, 1); } } //printf(" p=%lld, q=%lld\n", p, q); ll r = calcr(n, xs); ll s = calcr(n, ys); //printf(" r=%lld, s=%lld\n", r, s); double tau = (double)(p - q) / (sqrt(r) * sqrt(s)); printf("%.10lf\n", tau); return 0; }