//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using pii = pair; using pll = pair; using pli = pair; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' // 抽象再帰セグ木?(抽象セグ木の定義分からんな)(遅延ではない) // ococo_segtree rsq(n,0);みたいに宣言する template class ococo_segtree { T func(T a, T b) { // ここに演算を入れる return (a + b); } public: int n; T tmax; // range minimum query vector rmq; //(データの大きさ,単位元) ococo_segtree(int N, T t) { syokica(N, t); } // 配列の初期化 O(N) void syokica(int a, T t) { n = 1; tmax = t; while(n < a) n *= 2; rmq.resize(2 * n - 1); for(int i = 0; i < 2 * n - 1; i++) { rmq[i] = tmax; } } // a[i]をxにする O(logN) void update_num(int i, T x) { i += (n - 1); rmq[i] = x; while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } // a[i]にxを加える O(logN) void add_num(int i, T x) { i += (n - 1); rmq[i] = func(rmq[i], x); while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } T get_minimum2(int a, int b, int k, int l, int r) { if(a <= l && r <= b) return rmq[k]; else if(r <= a || b <= l) return tmax; else return func(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2), get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r)); } //[l,r)の区間演算の取得 O(logN) T get_val(int l, int r) { return get_minimum2(l, r, 0, 0, n); } }; //転倒数を返す関数 セグ木を前に貼る O(NlogN) same:同じ数が出てきた時転倒数にカウントするか long long ococo_tentousuu(vector a,bool same){ int n = a.size(); //座圧 vector temp(n); for(int i = 0; i < n; i++){ temp[i] = a[i]; } sort(temp.begin(),temp.end()); temp.erase(unique(temp.begin(),temp.end()),temp.end()); int m = temp.size(); for(int i = 0; i < n; i++){ a[i] = distance(temp.begin(),lower_bound(temp.begin(),temp.end(),a[i])); } //ここ、rsqなので注意!!!!!(セグ木の関数を場合によっては書き換える必要がある) ococo_segtree rsq(m,0); long long ans = 0; for(int i = 0; i < n; i++){ ans += rsq.get_val(a[i] + (same ? 0 : 1),m); rsq.add_num(a[i],1); } return ans; } #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //添え字回りで面倒になりそうなときは楽になる言い換えを実装の前にじっくり考える //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く int n; cin >> n; vector xy(n); for(int i = 0; i < n; i++){ cin >> xy[i].first >> xy[i].second; } sort(xy.begin(),xy.end()); vector y(n); for(int i = 0; i < n; i++)y[i] = xy[i].second; ll q = ococo_tentousuu(y,false); for(int i = 0; i < n; i++){ xy[i].first *= -1; } sort(xy.begin(),xy.end()); for(int i = 0; i < n; i++)y[i] = xy[i].second; ll p = ococo_tentousuu(y,false); map mpx,mpy; ll r = (ll)n * (ll)(n - 1) / 2; ll s = (ll)n * (ll)(n - 1) / 2; for(int i = 0; i < n; i++){ r -= mpx[xy[i].first]; mpx[xy[i].first]++; s -= mpy[xy[i].second]; mpy[xy[i].second]++; } cout << fixed << setprecision(15) << (long double)(p - q) / (long double)sqrt((long double)r * (long double)s) << el; return; } void calc(void){ return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }