n = read_line.to_i xys = Array.new(n) { read_line.split.map(&.to_i) } xs = xys.map { |v| v[0] }.uniq.sort ys = xys.map { |v| v[1] }.uniq.sort cols = Array.new(n) { [] of Int32 } rows = Array.new(n, 0) xys.each do |a| x, y = a xi = xs.bsearch_index { |v| v >= x }.not_nil! yi = ys.bsearch_index { |v| v >= y }.not_nil! cols[xi] << yi + 1 rows[yi] += 1 end r = n.to_i64 * (n - 1) // 2 s = n.to_i64 * (n - 1) // 2 p = 0i64 q = 0i64 bit = BIT(Int32).new(n + 1) cnt = 0i64 n.times do |x| cols[x].each do |y| p += bit.cumulative_sum(y - 1) q += cnt - bit.cumulative_sum(y) end cols[x].each do |y| bit.add(y, 1) end r -= cols[x].size.to_i64 * (cols[x].size - 1) // 2 cnt += cols[x].size s -= rows[x].to_i64 * (rows[x] - 1) // 2 end printf("%.9f\n", (p - q) / r ** 0.5 / s ** 0.5) class BIT(T) # 1-indexed def initialize(size : Int) len = 1 while len < size len *= 2 end @v = Array(T).new(len + 1, T.zero) end def cumulative_sum(index : Int) ret = T.zero while index > 0 ret += @v[index] index &= index - 1 end ret end def sum(l : Int, r : Int) cumulative_sum(r) - cumulative_sum(l - 1) end def add(index : Int, val : T) while index < @v.size @v[index] += val index += (index & -index) end end def set(index : Int, val : T) old = sum(index, index) add(index, val - old) end end