#include using namespace std; using SS = int; class SegmentTree{ public: int siz = 1,n; vector dat; SS op(SS a, SS b){return a+b;} SS e(){return 0;} void renew (SS &a,SS x){ a = op(a,x); //a = x; //その他. } void make(int N){ while(siz < N) siz *= 2; n = N; dat.resize(siz*2,e()); } void make2(int N,vector &A){ make(N); for(int i=0; i0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function f,int l = 0){ l += siz; int r = n+siz; vector ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function f,int r = -1){ if(r == -1) r = n; int l = siz; r += siz; vector ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } return 0; } //ノーマルセグ木.一年の時を経て漸く二分探索実装した. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N; cin >> N; vector> XY(N); vector all; for(auto &[x,y] : XY) cin >> x >> y,all.push_back(x),all.push_back(y); sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); vector Xs(2*N),Ys(2*N); map,long long> XYs; for(auto &[x,y] : XY){ x = lower_bound(all.begin(),all.end(),x)-all.begin(); y = lower_bound(all.begin(),all.end(),y)-all.begin(); Xs.at(x)++; Ys.at(y)++; XYs[{x,y}]++; } long long P = 0,Q = 0,R = 0,S = 0,ex = 0,pairs = N*(N-1)/2; for(auto &[k,v] : XYs) ex += v*(v-1)/2; for(auto &v : Xs) R += v*(v-1)/2; for(auto &v : Ys) S += v*(v-1)/2; sort(XY.begin(),XY.end()); int back = -1; vector memo; SegmentTree Z; Z.make(2*N); for(auto &[x,y] : XY){ if(x != back){ for(auto &p : memo) Z.update(p,1); memo.clear(); } back = x; P += Z.rangeans(0,y); memo.push_back(y); } Q = pairs-P-R-S+ex; R = pairs-R; S = pairs-S; cout << fixed << setprecision(20) << (P-Q+(long double)0.0)/sqrtl((long double)R*S) << endl; }