Problem:
 Score : 300 points    Problem Statement There are N towns in a coordinate plane. Town i is located at coordinates ( x_i , y_i ). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2} .  There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots , towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.      Constraints  2 \leq N \leq 8  -1000 \leq x_i \leq 1000  -1000 \leq y_i \leq 1000  \left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j )  (Added 21:12 JST) All values in input are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  :  x_N  y_N       Output Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6} .        Sample Input 1 3
0 0
1 0
0 1      Sample Output 1 2.2761423749  There are six paths to visit the towns: 1 → 2 → 3 , 1 → 3 → 2 , 2 → 1 → 3 , 2 → 3 → 1 , 3 → 1 → 2 , and 3 → 2 → 1 .  The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2} .  By calculating the lengths of the other paths in this way, we see that the average length of all routes is:  \frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...       Sample Input 2 2
-879 981
-866 890      Sample Output 2 91.9238815543  There are two paths to visit the towns: 1 → 2 and 2 → 1 . These paths have the same length.       Sample Input 3 8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310      Sample Output 3 7641.9817824387

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
arr=llint(n)
ans=0
cnt=0

for i in permutations(range(n)):
    cnt+=1
    for j in range(n-1):
        ans+=((arr[i[j]][0]-arr[i[j+1]][0])**2 + (arr[i[j]][1]-arr[i[j+1]][1])**2)**0.5

print(ans/cnt)

Solution (Python):
import itertools
import math

n = int(input())
x = [0]*n
y = [0]*n

for i in range(n):
    x[i], y[i] = map(int, input().split())

a = [list(e) for e in zip(x, y)]

c = list(itertools.permutations([i for i in range(n)]))

ans = [0]*len(c)

for i in range(len(c)):
    x_f = x[c[i][0]]
    y_f = y[c[i][0]]
    for j in range(1, n):
        x_s = x[c[i][j]]
        y_s = y[c[i][j]]

        ans[i] += math.sqrt((x_f-x_s)**2 + (y_f-y_s)**2)

        x_f = x[c[i][j]]
        y_f = y[c[i][j]]

print(sum(ans)/len(c))

Solution (Python):


from itertools import permutations
import numpy as np

def main():
    n = int(input())
    x = []
    y = []
    for i in range(n):
        xi, yi = map(int, input().split())
        x.append(xi)
        y.append(yi)

    odrs = permutations(list(range(n)), n)
    dists = [getdist(list(o), x, y) for o in odrs]
    print(np.mean(dists))

def getdist(odr, x, y):
    xo = np.array(x)[odr]
    yo = np.array(y)[odr]
    dx = xo[1:] - xo[:-1]
    dy = yo[1:] - yo[:-1]
    return np.sum((dx ** 2 + dy ** 2) ** 0.5)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations
from math import sqrt
n=int(input())
p_l=list(permutations(range(n)))

x=[]
for _ in range(n):
  x.append(list(map(int,input().split())))
n_fact=1
for i in range(n):
  n_fact*=(i+1)
ans=0
def dist(a,b):
  return sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]))
for i in p_l:
  su=0
 
  for j in range(1,len(i)):
    su+=dist(x[i[j-1]],x[i[j]])

  ans+=su
print(ans/n_fact)

Solution (Python):
import math
from itertools import permutations
n = int(input())
x, y = [0] * n, [0]*n
for i in range(n):
    x[i], y[i] = map(int, input().split())
    
dist = [[0]*n for _ in range(n)]
for i in range(n):
    for t in range(n):
        dist[i][t] = math.sqrt((x[i]-x[t])**2 + (y[i]-y[t])**2)
        
ans = 0
for p in permutations(range(n)):
    for i in range(len(p)-1):
        ans += dist[p[i]][p[i+1]]

print(ans / math.factorial(n))

Solution (Python):
import itertools

N = int(input())
v = []
for i in range(N):
    x,y = map(int, input().split())
    v.append((x,y))

res = 0
L = list(itertools.permutations(v))
for l in L:
    for i in range(1,len(l)):
        res += (abs(l[i][0]-l[i-1][0])**2 + abs(l[i][1]-l[i-1][1])**2)**.5
print(res/len(L))

Solution (Python):
from math import sqrt
from itertools import permutations

def dict(p, q):
    return sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)

n = int(input())
coord = []
for _ in range(n):
    coord.append([int(i) for i in input().split()])

sum = cnt = 0
for c in permutations(coord):
    for i in range(n-1):
        sum += dict(c[i], c[i+1])
    cnt += 1

print(sum/cnt)

Solution (Python):
from itertools import permutations
N=int(input())
xy=[tuple(map(int,input().split(' '))) for i in range(N)]
ans = 0
cnt = 0
for i in permutations([i for i in range(N)]):
    cnt += 1
    for j in range(N-1):
        ans += ((xy[i[j+1]][0]-xy[i[j]][0])**2+(xy[i[j+1]][1]-xy[i[j]][1])**2)**0.5
print(ans/cnt)

Solution (Python):
import numpy as np

N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
leng = 0
for i in range(N):
    for j in range(i+1, N):
        leng += np.sqrt((a[i][0]-a[j][0])**2 + (a[i][1]-a[j][1])**2)
print(2*leng/N)

Solution (Python):

import sys
import itertools
import math

def dist(sx, sy, dx, dy):
    return math.sqrt((sx - dx)**2 + (sy - dy)**2)


def solve(N, xs, ys):
    ps = [p for p in itertools.permutations(range(N))]
    total = 0
    for p in ps:
        for i in range(1, N):
            total += dist(xs[p[i]], ys[p[i]], xs[p[i-1]], ys[p[i-1]])
    print(total * 1.0 / len(ps))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    x = [int()] * (N)
    y = [int()] * (N)
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
import math

n = int(input())
town = [tuple(map(int, input().split())) for _ in range(n)]

D = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            D[i][j] = 0
        else:
            D[i][j] = math.sqrt((town[i][0]-town[j][0])**2 + (town[i][1]-town[j][1])**2)

print(sum([sum(k) for k in D]) / n)

Solution (Python):
import itertools
import math
def d(a,b):
  return math.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)

n = int(input())
cities = []
for i in range(n):
  cities.append(list(map(int,input().split())))

s = 0
fac = 1
for route in itertools.permutations([i for i in range(n)]):
  for i in range(len(route)-1):
    s += d(cities[route[i]],cities[route[i+1]])
print(s/math.factorial(n))

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import bisect
import re
import queue
from collections import Counter
from collections import defaultdict
from functools import lru_cache


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def map_float():
        return [float(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def PI():
        return math.acos(-1)

    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q

    def length(self):
        return len(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    
    n = Scanner.int()
    X = Scanner.int_list_list(n)
    ans = 0
    cnt = 0
    for v in itertools.permutations([i for i in range(n)]):
        len = 0
        for i in range(n - 1):
            a, b = v[i], v[i + 1]
            len += math.sqrt((X[a][0] - X[b][0]) ** 2 +
                             (X[a][1] - X[b][1]) ** 2)
        ans += len
        cnt += 1
    ans /= cnt
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
import math

n = int(input())
l = 0

x_list = []
y_list = []

for i in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

for j in range(n):
    for k in range(n):
        if j>=k:
            continue
        l += math.sqrt((x_list[j] - x_list[k]) ** 2 + (y_list[j] - y_list[k]) ** 2)

print(l * 2/n)

Solution (Python):
import math
n = int(input())
l = 0

x_list = []
y_list = []

for i in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

for j in range(n):
    for k in range(n):
        if j >= k:
            continue
        l += math.sqrt((x_list[j] - x_list[k]) ** 2 + (y_list[j] - y_list[k]) ** 2)

print(l * 2/n)

Solution (Python):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

import itertools
import math

path = 0
for ptn in itertools.permutations(range(n)):
    for i, j in zip(ptn, ptn[1:]):
        path += ((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2) ** 0.5
ans = path / (math.factorial(n))

print(ans)

Solution (Python):
import math
import itertools

N=int(input())
XY=[list(map(int,input().split())) for _ in range(N)]

ans=0
for v in itertools.permutations(range(N)):
    for i in range(N-1):
        ans+=math.sqrt((XY[v[i]][0]-XY[v[i+1]][0])**2+(XY[v[i]][1]-XY[v[i+1]][1])**2)

print(ans/math.factorial(N))

Solution (Python):
n = int(input())
list = [[int(j) for j in input().split()] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        ans += ((list[i][0] - list[j][0]) ** 2 + (list[i][1] - list[j][1]) ** 2) ** 0.5
print(ans / n)

Solution (Python):
import itertools
import math

N = int(input())
X = []
Y = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y)

num = [i for i in range(N)]
distance_list = []
for perm in itertools.permutations(num):
    prev = None
    distance = 0
    for v in perm:
        if prev is None:
            prev = v
        else:
            distance += math.sqrt((X[prev] - X[v]) ** 2 + (Y[prev] - Y[v]) ** 2)
    distance_list.append(distance)

print(sum(distance_list) / len(distance_list))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]

INF=float("inf")

n=int(input())
s = [list(map(int, input().split())) for i in range(n)]

from itertools import permutations
import math

sum=0
for p in permutations(range(n)):
    for i in range(n-1):
        sum+=(pow((s[p[i]][0]-s[p[i+1]][0]),2)+pow((s[p[i]][1]-s[p[i+1]][1]),2))**0.5
print(sum/math.factorial(n))

Solution (Python):
import math
import itertools

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]

ans = 0
for v in itertools.permutations(range(N)):
    for i in range(N-1):
        ans += math.sqrt((XY[v[i]][0]-XY[v[i+1]][0])**2 + (XY[v[i]][1]-XY[v[i+1]][1])**2)

print(ans/math.factorial(N))

Solution (Python):
n = int(input())
dat = []
import itertools
for _ in range(n):
    x, y = map(int, input().split())
    dat.append((x,y))
import math
allsum = 0
for a in itertools.permutations(range(n)):
    x, y = dat[a[0]]
    s = 0
    for b  in range(1, n):
        nx, ny = dat[a[b]]
        s += math.sqrt( (nx-x)**2 + (ny-y)**2 )
        x, y = nx, ny
    allsum += s
res = allsum / math.factorial(n)
print(res)

Solution (Python):
import itertools


n = int(input())
geo = [list(map(int, input().split())) for i in range(n)]

sum_dist = 0
num_pattern = 0

for pattern in itertools.permutations([i for i in range(n)], n):
    for i in range(1, n):
        x, y = geo[pattern[i]]
        x_prev, y_prev = geo[pattern[i-1]]
        d = ((x-x_prev) ** 2 + (y-y_prev) ** 2) ** 0.5
        sum_dist += d
    num_pattern += 1

print(sum_dist / num_pattern)

Solution (Python):
import itertools
import numpy as np
import math

def distance(a,b):
  dis = math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
  return dis

num_list = []
city_name = []
ans = []
num = int(input())
queue = np.zeros((num,num))

for i in range(num):
  num_list.append(list(map(int,input().split())))
  city_name.append(i+1)


com = list(itertools.permutations(city_name, 2))
way = list(itertools.permutations(city_name, num))

for i in range(0,len(com)):
  a = num_list[com[i][0]-1]
  b = num_list[com[i][1]-1]
  queue[com[i][1]-1][com[i][0]-1] = distance(a,b)

for i in range(0,len(way)):
  sum = 0
  for j in range(0,num-1):
    sum = sum + queue[way[i][j]-1][way[i][j+1]-1]
  ans.append(sum)

print(np.mean(ans))

Solution (Python):
import math
import itertools
N = int(input())
points = []
for _ in range(N):
    points.append(tuple(map(int, input().split(" "))))

distances = [[0 for _ in range(N)] for __ in range(N)]
for si in range(N):
    for ei in range(N):
        distances[si][ei] = ((points[si][0] - points[ei][0]) ** 2 +
                             (points[si][1] - points[ei][1]) ** 2) ** 0.5

total = 0
for route in itertools.permutations([i for i in range(N)]):
    for s, e in zip(route, route[1:]):
        total += distances[s][e]

print(total / math.factorial(N))

Solution (Python):
import sys
import math
from scipy.misc import comb  

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N - 1):
    for l in range(i + 1, N):
        ans += math.sqrt((xy[i][0] - xy[l][0]) ** 2 + (xy[i][1] - xy[l][1]) ** 2)
ans *= (N - 1) / comb(N, 2)
print(ans)

Solution (Python):
import math
n = int(input())
x = []
y = []
d = 0
for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    x.append(tmp1)
    y.append(tmp2)
for i in range(n):
    for j in range(i + 1, n):
        d += math.sqrt((x[i] - x[j]) ** 2 + ((y[i] - y[j]) ** 2))
print(d*2/n)

Solution (Python):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
L = list(itertools.permutations(xy))
ans = 0
for i in L:
    dis = 0
    for l in range(N-1):
        dis += math.sqrt((i[l][0]-i[l+1][0])**2 + (i[l][1] - i[l+1][1])**2)
    ans += dis
print(ans / len(L))

Solution (Python):
n = int(input())
x = [0]*n
y = [0]*n
for i in range(n):
  x1,y1 = map(int, input().split())
  x[i] = x1
  y[i] = y1

a = 0
b = 0
for i in range(n):
  t = list(range(n))
  t.remove(i)
  for j in t:
    a += ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
    b += 1
    
print(a*(n-1)/b)

Solution (Python):
from itertools import permutations as perm
from math import factorial

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

all_sum = 0
for a in perm(XY):
    sum_num = 0
    for j in range(N-1):
        x1, y1 = a[j]
        x2, y2 = a[j+1]
        r = (abs(x1-x2)**2 + abs(y1-y2)**2)**(1/2)
        sum_num += r
    all_sum += sum_num

print(all_sum / factorial(N))

Solution (Python):
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

t = 1
for i in range(1, N - 1):
  t *= i

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    x1, y1 = xy[i]
    x2, y2 = xy[j]
    ans += (((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2)) * (N - 1) * 2 * t

n = 1
for i in range(1, N + 1):
  n *= i

ans /= n

print(ans)

Solution (Python):
import math
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        D[i][j] = dist(A[i],A[j])
cnt = 0
for z in permutations(range(N),N):
    for i in range(N):
        cnt += D[z[i]][z[j]]
print(cnt/math.factorial(N))

Solution (Python):
import sys
import itertools
import math

N = int(sys.stdin.readline())

towns = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split(" "))
    towns.append((x, y))

dist = 0
count = 0
patterns = itertools.permutations(towns)
for pattern in patterns:
    count += 1
    pre_x, pre_y = 0, 0
    for i, (x, y) in enumerate(pattern):
        if i > 0:
            dist += math.sqrt((x - pre_x)**2 + (y - pre_y)**2)
        pre_x, pre_y = x, y

print(dist / count)

Solution (Python):
import itertools

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=0
for poss in itertools.permutations([i for i in range(n)]):
  for i in range(n-1):
    x1,y1=arr[poss[i]]
    x2,y2=arr[poss[i+1]]
    ans+=((x1-x2)**2+(y1-y2)**2)**0.5
for i in range(1,n+1):
  ans/=i
print(ans)

Solution (Python):
import math
import itertools


n = int(input())
town = dict()
for i in range(n):
    x, y = map(int, input().split())
    town[i] = [x, y]


def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)


total = 0
for p in itertools.permutations(town, n):
    bef = p[0]
    for i in p[1:]:
        total += distance(town[bef], town[i])
        bef = i

print(total/math.factorial(n))

Solution (Python):
from math import sqrt

N = int(input())

x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

sum = 0
for i in range(N):
    for j in range(N):
        if i != j:
            sum = sum + sqrt( (x[i] - x[j])*(x[i] - x[j])+(y[i] - y[j])*(y[i] - y[j]) )

print (sum/N)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inpuS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

from itertools import permutations

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
P = list(permutations(XY))
ans = 0
count = 0
for p in P:
  for i in range(1,len(p)):
    dist = ((p[i-1][0]-p[i][0])**2 + (p[i-1][1]-p[i][1])**2)
    ans += dist**0.5
print(ans/len(P))

Solution (Python):
def ABC106_B():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        
        return divisors
    N = I()
    ans = 0
    for i in range((N+1)//2):
        cur = i*2+1
        if len(make_divisors(cur))==8:
            ans += 1
    print(ans)
    return

def ABC122_B():
    S = SI()
    ans = 0
    cur = 0
    d = {"A","C","G","T"}
    for s in S:
        if s in d:
            cur += 1
        else:
            ans = max(ans,cur)
            cur = 0
    ans = max(ans,cur)
    print(ans)
    return

def paken2019_C():
    N, M = LI()
    A = [LI()for _ in range(N)]
    T = [i for i in range(M)]
    ans = 0
    for t1,t2 in itertools.permutations(T,2):
        cur = 0
        for i in range(N):
            cur += max(A[i][t1],A[i][t2])
        ans = max(ans,cur)
    print(ans)
    return

def ABC95_C():
    A, B, C, X, Y = LI()
    if A+B<=C*2:
        ans = A*X+B*Y
    else:
        if X>Y:
            ans = Y*C*2 + min(A,C*2)*(X-Y)
        else:
            ans = X*C*2 + min(B,C*2)*(Y-X)
    print(ans)
    return

def SMTB_D():
    def flag(n,s):
        for l in range(n,N):
            if S[l]==str(s):
                return l
        return N
    N = I()
    S = SI()
    ans = 0
    for i in range(10):
        L1 = flag(0,i)
        for j in range(10):
            L2 = flag(L1+1,j)
            for k in range(10):
                L3 = flag(L2+1,k)
                if L3<N:
                    ans += 1
                    
    print(ans)
    return

def JOI2007_3():
    N = I()
    V = [LI() for _ in range(N)]
    D = set()
    for vx,vy in V:
        D.add((vx,vy))
    ans = 0
    for i in range(N):
        a1, b1 = V[i]
        for j in range(i+1,N):
            a2, b2 = V[j]
            va, vb = a2 - a1, b2 - b1
            if (a1 + vb, b1 - va) in D and (a2 + vb, b2 - va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
            if (a1 - vb, b1 + va) in D and (a2 - vb, b2 + va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
    print(ans)
    return
"""
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
"""

def square869120Contest():
    def length(a,b,x,y):
        if x>y:
            x,y = y,x
        rep = 0
        if a<x:
            rep += (x-a)*2
        if y<b:
            rep += (b-y)*2
        rep += (y-x)
        return rep
    N = I()
    AB = [LI()for _ in range(N)]
    ans = inf
    for i in range(N):
        s = AB[i][0]
        for j in range(N):
            g = AB[j][1]
            cur = 0
            for k in range(N):
                cur += length(AB[k][0],AB[k][1],s,g)
            ans = min(ans,cur)
    print(ans)
    return

def JOI7_D():
    M = I()
    S = [LI()for _ in range(M)]
    Ss = [(0,0)]
    curx,cury = S[0]
    for sx,sy in S[1:]:
        Ss.append((sx-curx,sy-cury))
        curx = sx; cury = sy
    
    N = I()
    X = [LI()for _ in range(N)]
    D = set()
    for i in range(N):
        cur = (X[i][0],X[i][1])
        D.add(cur)
    for i in range(N):
        flag = True
        curx, cury = X[i]
        for k in range(M):
            curx += Ss[k][0]
            cury += Ss[k][1]
            
            if not (curx, cury) in D:
                flag = False
                break
        if flag:
            
            ansx = X[i][0] - S[0][0]
            ansy = X[i][1] - S[0][1]
            print(ansx,ansy)
            return
    return

def ABC128_C():
    N, M = LI()
    S = [[]for _ in range(N)]
    for i in range(M):
        s = LI()
        for j in s[1:]:
            S[j-1].append(i)
    P = LI()
    
    loop = 2**N
    ans = 0
    for i in range(loop):
        p = [0]*M
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j)
        for k in cur:
            for l in S[k]:
                p[l] += 1
        flag = True
        for j in range(M):
            if p[j]%2!=P[j]:
                flag = False
        if flag:
            ans += 1
    print(ans)
    return

def ABC2_D():
    N, M = LI()
    V = set()
    for _ in range(M):
        x,y = LI()
        V.add((x,y))
    loop = 2**N
    ans = 0
    
    for i in range(loop):
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j+1)
        flag = True
        for k1,k2 in itertools.permutations(cur,2):
            if not ((k1,k2) in V or (k2,k1) in V):
                flag = False
                break
        if flag:
            ans = max(ans,len(cur))
    print(ans)
    return

def JOI7_E():
    R, C = LI()
    A = [LI()for _ in range(R)]
    loop = 2**R
    ans = 0
    for i in range(loop):
        rev = set()
        for j in range(R):
            if (1<<j)&i==(1<<j):
                rev.add(j)
        cur = 0
        for j in range(C):
            s = 0
            for k in range(R):
                if k in rev and A[k][j]==0:
                    s += 1
                elif (not k in rev) and A[k][j]==1:
                    s += 1
            cur += max(s,R-s)
        ans = max(ans,cur)
    print(ans)
    return

def square869120Contest4_B():
    N, K = LI()
    A = LI()
    ans = inf
    loop = 2**(N-1)
    for i in range(loop):
        look = set()
        for j in range(N-1):
            if (1<<j)&i==(1<<j):
                look.add(j+1)
        if len(look)<K-1:
            continue
        high = A[0]
        cur = 0
        flag = True
        for j in range(1,N):
            if not (j in look):
                if A[j]>high:
                    flag = False
                    break
            else:
                if high >= A[j]:
                    cur += (high - A[j] + 1)
                    high += 1
                else:
                    high = A[j]
        
        if not flag:
            continue
        ans = min(ans,cur)
    print(ans)
    return

def ABC145_C():
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    c = 0
    for x in itertools.permutations(X):
        cur = 0
        c += 1
        for i in range(N-1):
            cur += ((x[i+1][0]-x[i][0])**2 + (x[i+1][1]-x[i][1])**2)**0.5
        ans += cur
    ans /= c
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC145_C()

"""

"""

Solution (Python):
import math
N = int(input())
X = []
ans = 0
for i in range(N):
    x = list(map(int, input().split()))
    X.append(x)
for j in range(N):
    for k in range(N):
        Y = (X[j][0]-X[k][0])**2 + (X[j][1]-X[k][1])**2
        ans += math.sqrt(Y)*math.factorial(N-1)
print(ans/math.factorial(N))

Solution (Python):
import itertools
import math

def CalcDistance(x1, y1, x2, y2):
	return ((x1-x2)**2 + (y1-y2)**2)**(1/2)

N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
	x[i], y[i] = map(int, input().split())

distance = 0
Town = range(N)
for Route in itertools.permutations(Town,N):
	for TownNum in range(N-1):
		distance += CalcDistance(x[Route[TownNum]], y[Route[TownNum]], x[Route[TownNum+1]], y[Route[TownNum+1]])

print(distance/math.factorial(N))

Solution (Python):
import itertools

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for trans in itertools.permutations(range(N)):
	distance = 0
	for i in range(1,N):
		ind_2, ind_1 = trans[i], trans[i-1]
		x2,y2 = XY[ind_2]
		x1,y1 = XY[ind_1]
		distance += ((x2-x1)**2 + (y2-y1)**2)**(1/2)

	ans += distance

for i in range(1,N+1):
	ans /= i

print(ans)

Solution (Python):

import sys
from itertools import permutations
from math import sqrt

def inpl(): return list(map(int, input().split()))
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i], Y[i] = inpl()
sum_ = 0
cnt_ = 0
for P in permutations(range(N)):
    cnt_ += 1
    for i in range(N-1):
        sum_ += sqrt(pow(X[P[i+1]]-X[P[i]], 2) + pow(Y[P[i+1]] - Y[P[i]], 2))

print(sum_/cnt_)

Solution (Python):
import itertools
import math
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
waru = math.factorial(N)
ans = 0
total = 0
for i in itertools.permutations(xy, N):
    for j in range(1, N):
        total += ((i[j - 1][0] - i[j][0]) ** 2 + (i[j - 1][1] - i[j][1]) ** 2) ** 0.5

print(total / waru)

Solution (Python):
import math
n=int(input())
base = math.factorial(n-1)
p = []
for i in range(n):
    x,y=map(int,input().split())
    p.append((x,y))

l=0
for i in range(n):
    for j in range(i+1,n):
        l += math.sqrt((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)*base*2
print(l/math.factorial(n))

Solution (Python):
import math
import itertools


def dist(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1] - b[1])**2)


def length(P, p):
    total = 0
    for i in range(len(p)-1):
        total += dist(P[p[i]], P[p[i+1]])
    return total


N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

print(sum([length(P, p)
           for p in itertools.permutations(range(N))]) / math.factorial(N))

Solution (Python):
from itertools import permutations

n = int(input())
*ps, = (tuple(map(int, input().split())) for _ in range(n))

ret = 0
for perm in permutations(ps):
    it = iter(perm)
    p = next(it)
    for q in it:
        ret += ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5
        p = q


def fact(n):
    if n == 0: return 1
    return n * fact(n - 1)


ret /= fact(n)

print(ret)

Solution (Python):
import math
import itertools

n=int(input())
town=[]
length=0
pattern=math.factorial(n)
for i in range(n):
    tmp=list(map(int,input().split()))
    town.append(tmp)
town_all=list(itertools.permutations(town))
for i in town_all:
    for j in range(n-1):
        x_length=(i[j+1][0]-i[j][0])**2
        y_length=(i[j+1][1]-i[j][1])**2
        length+=math.sqrt(x_length+y_length)

print(length/pattern)

Solution (Python):
from itertools import permutations
from math import factorial

N = int(input())
co = [tuple(map(int, input().split())) for _ in range(N)]
total = 0
for path in permutations(range(N)):
    for i, j in zip(path[0:N - 1], path[1:]):
        total += ((co[i][0] - co[j][0]) ** 2 + (co[i][1] - co[j][1]) ** 2) ** 0.5
print(total / factorial(N))