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-----
3
0 0
1 0
0 1

-----Sample Output-----
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...

Source: atcoder | Difficulty: EASY


Solutions:
import itertools
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

def factorization(n):
	if n == 1:
		return 1
	return n * factorization(n - 1)
size = factorization(n)
a = list(itertools.permutations(l, n))
total = 0
for i in range(size):
	for j in range(n - 1):
		x1 = a[i][j][0]
		x2 = a[i][j + 1][0]
		y1 = a[i][j][1]
		y2 = a[i][j + 1][1]
		x_total = (x1 - x2) ** 2
		y_total = (y1 - y2) ** 2
		total += (x_total + y_total) ** 0.5
print(total / size)


import math
n = int(input())
xy = []
for i in range(n):
	xy.append(list(map(int, input().split())))
ans = 0
for j in range(n):
	for i in range(n):
		ans += math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2)
print(ans / n)


import itertools
import math
N = int(input())
L = [list(map(int, input().split())) for n in range(N)]
I = list(itertools.permutations(L))
sum = 0
for i in I:
	for n in range(N - 1):
		sum += math.sqrt((i[n + 1][0] - i[n][0]) ** 2 + (i[n + 1][1] - i[n][1]) ** 2)
print(sum / len(I))


xy = [[*map(int, input().split())] for _ in range(int(input()))]
print(sum((((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) ** 0.5 for j in xy for i in xy)) / len(xy))


import numpy as np
n = int(input())
a = np.array([list(map(int, input().split())) for i in range(n)])
c = 0
for i in a:
	for j in a:
		c += np.linalg.norm(i - j)
print(c / n)


def II():
	return int(input())

def LII():
	return list(map(int, input().split()))
n = II()
town = [LII() for _ in range(n)]
distance = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		[xi, yi] = town[i]
		[xj, yj] = town[j]
		distance += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
print(distance * 2 / n)


N = int(input())
locs = []
S = 0
for _ in range(N):
	locs.append(list(map(int, input().split())))
for i in range(N):
	for j in range(i + 1, N):
		dis = ((locs[i][0] - locs[j][0]) ** 2 + (locs[i][1] - locs[j][1]) ** 2) ** (1 / 2)
		S += dis
print(2 * S / N)


import math
ini = lambda : int(input())
inm = lambda : map(int, input().split())
inl = lambda : list(map(int, input().split()))
gcd = lambda x, y: gcd(y, x % y) if x % y else y

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

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)
	divisors.sort()
	return divisors

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
mod = 10 ** 9 + 7
n = ini()
k = []
for i in range(n):
	k.append(inl())
sm = 0
for (x, y) in k:
	for (xd, yd) in k:
		sm += ((x - xd) ** 2 + (y - yd) ** 2) ** 0.5
print(sm / n)


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

def getDistance(A, B):
	x = A[0] - B[0]
	y = A[1] - B[1]
	return (x ** 2 + y ** 2) ** 0.5
totalDistance = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		totalDistance += getDistance(sites[i], sites[j])
print(2 * totalDistance / N)


import itertools
import math
n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
p = itertools.permutations(list(range(n)), n)
lenlist = []
for v in p:
	len = 0
	for i in range(n - 1):
		len += ((xy[v[i + 1]][0] - xy[v[i]][0]) ** 2 + (xy[v[i + 1]][1] - xy[v[i]][1]) ** 2) ** 0.5
	lenlist.append(len)
print(sum(lenlist) / math.factorial(n))


import itertools
import math
n = int(input())
path = []
for i in range(n):
	(x, y) = map(int, input().split())
	path.append([x, y])
distance = []
visitedPath = list(itertools.permutations(path))
for vp in visitedPath:
	routeDistance = 0
	for i in range(len(vp) - 1):
		routeDistance += math.sqrt((vp[i][0] - vp[i + 1][0]) ** 2 + (vp[i][1] - vp[i + 1][1]) ** 2)
	distance.append(routeDistance)
print(sum(distance) / len(distance))


import itertools
import math
N = int(input())
pos = [list(map(int, input().split())) for _ in range(N)]
Cases = itertools.permutations([x for x in range(N)])
ans = 0
for case in Cases:
	for i in range(N - 1):
		(x, y) = list(map(int, pos[case[i]]))
		(nx, ny) = list(map(int, pos[case[i + 1]]))
		tmp = math.sqrt((nx - x) ** 2 + (ny - y) ** 2)
		ans += tmp
ans /= math.factorial(N)
print(ans)


import itertools
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xy_d = [[0] * N for _ in range(N)]
xylist = list(itertools.permutations([n for n in range(N)], N))
for i in range(N - 1):
	for h in range(i + 1, N):
		xy_d[i][h] = ((xy[i][0] - xy[h][0]) ** 2 + (xy[i][1] - xy[h][1]) ** 2) ** 0.5
		xy_d[h][i] = ((xy[i][0] - xy[h][0]) ** 2 + (xy[i][1] - xy[h][1]) ** 2) ** 0.5
ans = 0
for g in range(len(xylist)):
	for t in range(N - 1):
		ans += xy_d[xylist[g][t]][xylist[g][t + 1]]
print(ans / len(xylist))


def dfs(pi):
	if len(pi) == n:
		p.append(pi)
		return
	for i in range(1, n + 1):
		if i in pi:
			continue
		cpi = pi + (i,)
		dfs(cpi)
n = int(input())
p = []
dfs(tuple())
pos = []
pos.append(-1)
for i in range(n):
	(x, y) = list(map(int, input().split()))
	pos.append((x, y))
dist = 0
for v in p:
	d = 0
	for i in range(len(v) - 1):
		pos1 = v[i]
		pos2 = v[i + 1]
		(xi, yi) = pos[pos1]
		(xj, yj) = pos[pos2]
		d += ((xi - xj) ** 2 + (yi - yj) ** 2) ** (1 / 2)
	dist += d
print(dist / len(p))


import itertools
n = int(input())
town = []
for i in range(n):
	(x, y) = map(int, input().split())
	town.append((x, y))
cnt = 0
length = 0
for t in itertools.permutations(town):
	for i in range(n - 1):
		x = (t[i][0] - t[i + 1][0]) ** 2
		y = (t[i][1] - t[i + 1][1]) ** 2
		length += (x + y) ** 0.5
	cnt += 1
print(length / cnt)


import sys
from itertools import islice, permutations

def resolve(in_):
	N = int(next(in_))
	XY = tuple((tuple(map(int, line.split())) for line in islice(in_, N)))
	count = 0
	distance = 0.0
	for towns in permutations(list(range(N))):
		count += 1
		town0 = towns[0]
		for town1 in towns[1:]:
			(x0, y0) = XY[town0]
			(x1, y1) = XY[town1]
			distance2 = (x1 - x0) ** 2 + (y1 - y0) ** 2
			distance += distance2 ** 0.5
			town0 = town1
	average = distance / count
	return '{:.7f}'.format(average)

def main():
	answer = resolve(sys.stdin)
	print(answer)

def __starting_point():
	main()
__starting_point()


import math
from itertools import permutations
N = int(input())
XYlist = []
indexlist = [i for i in range(N)]
for _ in range(N):
	XYlist.append(tuple(map(int, input().split())))
ans = 0
num = 0
for indexes in permutations(indexlist, N):
	for i in range(N - 1):
		ans += math.sqrt((XYlist[indexes[i]][0] - XYlist[indexes[i + 1]][0]) ** 2 + (XYlist[indexes[i]][1] - XYlist[indexes[i + 1]][1]) ** 2)
	num += 1
print(ans / num)


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])
(dy8, dx8) = ([0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def sum_of_arithmetic_progression(s, d, n):
	return n * (2 * s + (n - 1) * d) // 2

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	g = gcd(a, b)
	return a / g * b

def calc(p, P):
	ans = 0
	for i in range(1, len(p)):
		(x1, y1) = P[p[i - 1]]
		(x2, y2) = P[p[i]]
		ans += sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
	return ans

def solve():
	N = int(input())
	P = []
	for _ in range(N):
		(X, Y) = list(map(int, input().split()))
		P.append((X, Y))
	ans = 0
	num = 0
	for p in permutations(list(range(N))):
		ans += calc(p, P)
		num += 1
	print(ans / num)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


import math
import itertools
N = int(input())
arr = []
for _ in range(N):
	(x, y) = map(int, input().split())
	arr.append((x, y))
p = list(itertools.permutations(arr))
d = 0.0
for pair in p:
	for (a, b) in zip(pair[0:], pair[1:]):
		d += math.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)
print(d / len(p))


import itertools, math
N = int(input())
lst1 = []
for _ in range(N):
	(x, y) = map(int, input().split())
	lst1.append((x, y))
lst2 = list(itertools.combinations(lst1, 2))
p = math.factorial(N) * (N - 1)
c = len(list(itertools.combinations(lst1, 2)))
total = 0
for i in lst2:
	d = ((i[1][0] - i[0][0]) ** 2 + (i[1][1] - i[0][1]) ** 2) ** 0.5
	total += d
num = int(p / c)
fct = math.factorial(N)
print(total * num / fct)


N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]
from math import hypot, factorial
distance = []
for (i, j) in D:
	for (k, l) in D:
		distance.append(hypot(i - k, j - l))
print(sum(distance) / N)


import itertools
import math
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
q = list(itertools.permutations(range(n)))
m = len(q)
k_sum = 0
for i in range(m):
	for j in range(n - 1):
		a = xy[q[i][j]][0] - xy[q[i][j + 1]][0]
		x = a ** 2
		b = xy[q[i][j]][1] - xy[q[i][j + 1]][1]
		y = b ** 2
		k_sum += math.sqrt(x + y)
print(k_sum / m)


import sys
import numpy as np
input = sys.stdin.readline

def slove():
	N = int(input())
	town_position = np.array([list(map(float, input().split())) for i in range(N)])
	distance = 0
	for i in range(N - 1):
		(x1, y1) = town_position[i]
		for j in range(i + 1, N):
			(x2, y2) = town_position[j]
			distance += np.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
	ans = distance * 2 / N
	print(ans)

def __starting_point():
	slove()
__starting_point()


import itertools
n = int(input())
town = [list(map(int, input().split())) for _ in range(n)]
x = 1
for i in range(1, n + 1):
	x *= i
l = []
for j in range(n):
	l.append(j)
ans = 0
for a in itertools.permutations(l, n):
	newl = a
	length = 0
	for b in range(n - 1):
		length += ((town[newl[b]][0] - town[newl[b + 1]][0]) ** 2 + (town[newl[b]][1] - town[newl[b + 1]][1]) ** 2) ** (1 / 2)
	ans += length
print(ans / x)


from itertools import permutations
import math
n = int(input())
(x, y) = ([], [])
for _ in range(n):
	(x_, y_) = map(int, input().split())
	x.append(x_)
	y.append(y_)
c = list(permutations([i for i in range(1, n + 1)], n))
sum = 0
for ci in c:
	tmp = 0
	for i in range(len(ci) - 1):
		tmp += math.sqrt((x[ci[i] - 1] - x[ci[i + 1] - 1]) ** 2 + (y[ci[i] - 1] - y[ci[i + 1] - 1]) ** 2)
	sum += tmp
print(sum / len(c))


import itertools
import math

def calc_dist(pos1, pos2):
	(x1, y1) = pos1
	(x2, y2) = pos2
	return math.sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))
N = int(input())
distance_mat = [[-1000 for _ in range(N)] for _ in range(N)]
pos = []
for _ in range(N):
	pos.append(list(map(int, input().split())))
perms = itertools.permutations(list(range(N)), N)
result = []
for perm in perms:
	dist_sum = 0
	for i in range(1, N):
		source = perm[i - 1]
		sink = perm[i]
		if distance_mat[source][sink] == -1000:
			dist = calc_dist(pos[source], pos[sink])
			distance_mat[source][sink] = dist
			distance_mat[sink][source] = dist
		else:
			dist = distance_mat[source][sink]
		dist_sum += dist
	result.append(dist_sum)
import numpy as np
print(np.average(result))


import itertools
N = int(input())
x = []
y = []
for i in range(N):
	xy = list(map(int, input().split()))
	x.append(xy[0])
	y.append(xy[1])
l = [i for i in range(N)]
ans = 0
cnt = 0
for i in itertools.permutations(l, N):
	cnt += 1
	for j in range(1, N):
		x1 = x[i[j]]
		x2 = x[i[j - 1]]
		y1 = y[i[j]]
		y2 = y[i[j - 1]]
		ans += pow((x1 - x2) ** 2 + (y1 - y2) ** 2, 0.5)
ans /= cnt
print(ans)


import numpy as np
import itertools
N = int(input())
XY = []
for _ in range(N):
	(x, y) = list(map(int, input().split()))
	XY.append([x, y])
D = np.zeros((N, N))
for i in range(N - 1):
	(xi, yi) = (XY[i][0], XY[i][1])
	for j in range(i + 1, N):
		(xj, yj) = (XY[j][0], XY[j][1])
		distance = np.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
		D[i][j] = distance
		D[j][i] = distance
ans = 0
for l in itertools.permutations(list(range(N))):
	dis = 0
	for i in range(N - 1):
		dis += D[l[i]][l[i + 1]]
	ans += dis
print(ans / np.math.factorial(N))


from itertools import permutations
import math
n = int(input())
x = []
y = []
for i in range(n):
	(xi, yi) = map(int, input().split(' '))
	x.append(xi)
	y.append(yi)
l = [i for i in range(n)]
route = list(permutations(l))
length = 0
for ls in route:
	for i in range(n - 1):
		length += math.sqrt((x[ls[i + 1]] - x[ls[i]]) ** 2 + (y[ls[i + 1]] - y[ls[i]]) ** 2)
ans = length / math.factorial(n)
print(ans)


import math
from itertools import permutations

def calc_distance(a, b):
	dx = a[0] - b[0]
	dy = a[1] - b[1]
	d = math.sqrt(dx * dx + dy * dy)
	return d
N = int(input())
city = [0] * N
for i in range(N):
	city[i] = list(map(int, input().split()))
mtx = [0 for i in range(N)] * N
mtx = [[calc_distance(a, b) for a in city] for b in city]
all_distance = 0
paths = permutations([i for i in range(N)])
cnt = 0
for pt in paths:
	distance = 0
	for idx in range(1, len(pt)):
		distance += mtx[pt[idx]][pt[idx - 1]]
	all_distance += distance
	cnt += 1
all_distance /= cnt
print(all_distance)


import math

def perm(s, a, d, j):
	l = len(s)
	if l == 0:
		a.append(d.copy())
	else:
		for i in range(0, l):
			d[j] = s[i]
			perm(s[0:i] + s[i + 1:], a, d, j + 1)

def per(N, a):
	s = list(range(1, N + 1))
	d = list(range(1, N + 1))
	j = 0
	perm(s, a, d, j)
N = int(input())
a = []
per(N, a)
x = [0] * N
y = [0] * N
for i in range(0, N):
	(x[i], y[i]) = map(int, input().split())
M = len(a)
S = 0
for j in range(0, M):
	for i in range(0, N - 1):
		S += math.sqrt((x[a[j][i] - 1] - x[a[j][i + 1] - 1]) ** 2 + (y[a[j][i] - 1] - y[a[j][i + 1] - 1]) ** 2)
print(S / M)


n = int(input())
x_y = []
for _ in range(n):
	x_y.append([int(i) for i in input().split()])
import itertools
import math
ans = 0.0
for x_yi in itertools.permutations(x_y, n):
	sum_ = 0.0
	for i in range(n - 1):
		sum_ += math.sqrt((x_yi[i][0] - x_yi[i + 1][0]) ** 2 + (x_yi[i][1] - x_yi[i + 1][1]) ** 2)
	ans += sum_ / math.factorial(n)
print(ans)


from math import factorial
from itertools import permutations
n = int(input())
(t, *c) = [list(map(int, input().split())) for _ in range(n)]
print(sum((sum((((x - v) ** 2 + (y - w) ** 2) ** 0.5 for ((x, y), (v, w)) in zip([t] + l, l + [t]))) for l in map(list, permutations(c)))) * (n - 1) / factorial(n))


import itertools
import math

def main():
	lists = []
	N = int(input())
	lists = [list(map(int, input().split())) for _ in range(N)]
	ans = 0
	length = 0
	for line in itertools.permutations(lists):
		a = []
		b = []
		for data in line:
			if len(b) == 0:
				b = data
				continue
			else:
				a = b
				b = data
				length = math.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)
				ans += length
	print(ans / math.factorial(N))

def __starting_point():
	main()
__starting_point()


import math
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
result = 0
for i in range(N):
	for j in range(N):
		if i != j:
			result += math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2)
print(result / N)


import itertools, math
N = int(input())
(ls, L) = ([], 0)
for i in range(N):
	(x, y) = map(int, input().split(' '))
	ls.append([x, y])
perms = itertools.permutations(range(N))
for perm in perms:
	for i in range(N - 1):
		L += math.sqrt((ls[perm[i + 1]][0] - ls[perm[i]][0]) ** 2 + (ls[perm[i + 1]][1] - ls[perm[i]][1]) ** 2)
print(L / math.factorial(N))


import itertools
import math
N = int(input())
p = []
for i in range(N):
	(x, y) = [int(n) for n in input().split()]
	p.append([x, y])
total_length = 0
k = 0
for pattern in itertools.permutations(p):
	k += 1
	length = 0
	for i in range(N - 1):
		length += math.sqrt((pattern[i + 1][0] - pattern[i][0]) ** 2 + (pattern[i + 1][1] - pattern[i][1]) ** 2)
	total_length += length
print(total_length / k)


from itertools import permutations
from math import sqrt
N = int(input())
xy = [input().split() for _ in range(N)]
xy = [[int(x), int(y)] for (x, y) in xy]
distance = 0
P = list(permutations(xy, N))
for r in P:
	temp = None
	for i in r:
		if not temp:
			temp = i
			continue
		distance += sqrt((temp[0] - i[0]) ** 2 + (temp[1] - i[1]) ** 2)
		temp = i
print(distance / len(P))


import math
import itertools

def calc(x1y1, x2y2):
	(x1, y1) = x1y1
	(x2, y2) = x2y2
	return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
N = int(input())
addresses = []
for _ in range(N):
	addresses.append(list(map(int, input().split())))
ways = list(itertools.permutations(list(range(N))))
ans = 0
for x in ways:
	dist = 0
	for i in range(N - 1):
		dist += calc(addresses[x[i]], addresses[x[i + 1]])
	ans += dist
print(ans / len(ways))


3
import sys
from itertools import permutations
from math import factorial
input = lambda : sys.stdin.readline().strip()
n = int(input())
coords = [[int(x) for x in input().split()] for _ in range(n)]
print(f'{sum((((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2) ** 0.5 for p in permutations(coords) for (i, j) in zip(p, p[1:]))) / factorial(n):.6f}')


import itertools
N = int(input())
A = []
for n in range(N):
	(x, y) = map(int, input().split())
	A.append((x, y))
pattern = itertools.permutations(A, N)
temp = 0
number = 0
for i in pattern:
	number += 1
	for j in range(len(i) - 1):
		temp += ((i[j][0] - i[j + 1][0]) ** 2 + (i[j][1] - i[j + 1][1]) ** 2) ** 0.5
print(temp / number)


import sys, math, itertools
n = int(input())
towns = [[int(x) for x in row.split()] for row in sys.stdin.readlines()]
counter = 0
final_sum = 0
for town_list in itertools.permutations(towns):
	counter += 1
	sum = 0
	for (i, town) in enumerate(town_list):
		if i == 0:
			old_town = town
		else:
			length = math.sqrt((town[0] - old_town[0]) ** 2 + (town[1] - old_town[1]) ** 2)
			sum += length
			old_town = town
	final_sum += sum
print(final_sum / counter)


import itertools
n = int(input())
s = ''.join([str(_) for _ in range(n)])
l = list(itertools.permutations(s, n))
x = []
y = []
for i in range(n):
	(xi, yi) = map(int, input().split())
	x.append(xi)
	y.append(yi)
c = 0.0
for j in l:
	for k in range(n - 1):
		c += ((x[int(j[k])] - x[int(j[k + 1])]) ** 2 + (y[int(j[k])] - y[int(j[k + 1])]) ** 2) ** 0.5
print(c / len(l))


from itertools import permutations
import sys
import math
pin = sys.stdin.readline

def main():
	N = int(pin())
	d = [list(map(int, pin().split())) for _ in [0] * N]
	l = list(permutations(list(range(N))))
	k = 0
	for i in l:
		s = 0
		for j in range(N - 1):
			x = (d[i[j]][0] - d[i[j + 1]][0]) ** 2
			y = (d[i[j]][1] - d[i[j + 1]][1]) ** 2
			s += math.sqrt(x + y)
		k += s
	ans = k / len(l)
	print(ans)
	return
main()


import numpy as np
N = int(input())
xy = [list(map(int, input().split(' '))) for i in range(N)]
L = 0
for i in range(N):
	for j in range(N):
		a = xy[i][0] - xy[j][0]
		b = xy[i][1] - xy[j][1]
		l = np.sqrt(a ** 2 + b ** 2)
		L += l
print(L / N)


def func(n):
	if n == 1:
		return 1
	return n * func(n - 1)
n = int(input())
L = [0 for i in range(n)]
for i in range(n):
	L[i] = list(map(int, input().split()))
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		length = (L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2
		length = length ** 0.5
		ans += length * func(n - 1) * 2
print(ans / func(n))


N = int(input())
cities = [tuple(map(int, input().split())) for i in range(N)]
from collections import defaultdict
dist = defaultdict(int)
import itertools
for perm in itertools.permutations(range(N), 2):
	(x1, y1) = cities[perm[0]]
	(x2, y2) = cities[perm[1]]
	dist[perm] = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
ans = 0
cnt = 0
for perm in itertools.permutations(range(N), N):
	cnt += 1
	for i in range(1, len(perm)):
		ans += dist[perm[i - 1], perm[i]]
print(ans / cnt)


from collections import deque
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

def dist(a, b):
	return pow(pow(b[0] - a[0], 2) + pow(b[1] - a[1], 2), 1 / 2)
que = deque([[i] for i in range(N)])
perm = []
while que:
	seq = que.popleft()
	if len(seq) == N:
		perm.append(seq)
	for j in range(N):
		if j not in seq:
			que.append(seq + [j])
d = 0
s = len(perm)
for p in perm:
	for k in range(N - 1):
		d += dist(xy[p[k]], xy[p[k + 1]])
print(d / s)


import math
N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
ave = 0
cnt = 0
import itertools
for v in itertools.permutations([int(x) for x in range(N)], N):
	for i in range(1, len(v)):
		ave += math.sqrt((xy[v[i - 1]][0] - xy[v[i]][0]) ** 2 + (xy[v[i - 1]][1] - xy[v[i]][1]) ** 2)
	cnt += 1
ave = ave / cnt
print(ave)


import itertools
import math
N = int(input())
citys = []
for i in range(N):
	citys.append([int(x) for x in input().split()])
a = list(itertools.permutations(list(range(N)), N))
ans = 0
for i in a:
	b = 0
	for j in range(N - 1):
		b += math.sqrt((citys[i[j]][0] - citys[i[j + 1]][0]) ** 2 + (citys[i[j]][1] - citys[i[j + 1]][1]) ** 2)
	ans += b
print(ans / len(a))


3
import math
N = int(input())
P = [[int(x) for x in input().split()] for _ in range(N)]

def calc(path):
	r = 0
	for i in range(len(path) - 1):
		p1 = P[path[i - 1]]
		p2 = P[path[i]]
		dx = p1[0] - p2[0]
		dy = p1[1] - p2[1]
		r += math.sqrt(dx * dx + dy * dy)
	return r
ret = 0
numret = 0

def rec(path, rest):
	if not rest:
		nonlocal ret
		nonlocal numret
		ret += calc(path)
		numret += 1
		return
	for i in range(len(rest)):
		rec(path + [rest[i]], rest[:i] + rest[i + 1:])
rec([], [i for i in range(N)])
print(ret / numret)


from itertools import permutations
N = int(input())
XY = []
for _ in range(N):
	(x, y) = list(map(int, input().split()))
	XY.append((x, y))
ans = 0
c = 0
for p in permutations(list(range(N))):
	dist = 0
	(x1, y1) = XY[p[0]]
	for i in p[1:]:
		(x, y) = XY[i]
		dist += ((x1 - x) ** 2 + (y1 - y) ** 2) ** 0.5
	ans += dist
	c += 1
print(ans / c)


from sys import stdin
import math
import itertools
n = int(stdin.readline().rstrip())
x = [0] * n
y = [0] * n
v = [0] * n
for i in range(n):
	(x[i], y[i]) = [int(x) for x in stdin.readline().rstrip().split()]
	v[i] = i
cnt = 0
ans = 0
for idx in list(itertools.permutations(v)):
	cnt += 1
	for i in range(1, n):
		ans += math.sqrt((x[idx[i]] - x[idx[i - 1]]) * (x[idx[i]] - x[idx[i - 1]]) + (y[idx[i]] - y[idx[i - 1]]) * (y[idx[i]] - y[idx[i - 1]]))
print(ans / cnt)


import math
import itertools
n = int(input())
pos = []
for i in range(n):
	(x, y) = map(int, input().split())
	pos.append([x, y])
iter = list(itertools.permutations(list(range(n))))
total = 0
for i in iter:
	for j in range(n - 1):
		p1 = pos[i[j]]
		p2 = pos[i[j + 1]]
		d = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
		total += d
print(total / len(iter))


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


import itertools
N = int(input())
X = []
Y = []
seq = list(itertools.permutations([i for i in range(1, N + 1)]))
a = 0
for i in range(N):
	(x, y) = map(int, input().split())
	X.append(x)
	Y.append(y)
for h in range(len(seq)):
	for i in range(N - 1):
		a += ((X[seq[h][i] - 1] - X[seq[h][i + 1] - 1]) ** 2 + (Y[seq[h][i] - 1] - Y[seq[h][i + 1] - 1]) ** 2) ** 0.5
print(a / len(seq))


import itertools
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ans = []
for i in itertools.permutations([i for i in range(n)]):
	tmp = 0
	for j in range(1, n):
		tmp += ((xy[i[j]][0] - xy[i[j - 1]][0]) ** 2 + (xy[i[j]][1] - xy[i[j - 1]][1]) ** 2) ** 0.5
	ans.append(tmp)
print(sum(ans) / len(ans))


N = int(input())
city = [list(map(int, input().split())) for _ in range(N)]
d = 0
for i in range(N):
	for j in range(N):
		d += ((city[i][0] - city[j][0]) ** 2 + (city[i][1] - city[j][1]) ** 2) ** 0.5
print(d / N)


import math
n = int(input())
towns = [list(map(int, input().split())) for _ in range(n)]
ans = 0
c = 0
for i in range(n - 1):
	(x1, y1) = towns[i]
	for j in range(i + 1, n):
		(x2, y2) = towns[j]
		ans += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) * (n - 1) * 2
print(ans / ((n - 1) * n))


import math
n = int(input())
t = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in range(n):
	(x, y) = t[i]
	for j in range(i, n):
		(x1, y1) = t[j]
		ans += math.sqrt((x - x1) ** 2 + (y - y1) ** 2) * (n - 1) * 2
print(ans / ((n - 1) * n))


import math
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
	(x[i], y[i]) = list(map(int, input().split()))
q = 2
for i in range(2, n):
	q *= i
s = 0.0
for i in range(n - 1):
	for j in range(i, n):
		s += math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) * q
f = math.factorial(n)
print(s / f)


from itertools import permutations
import math
N = int(input())
s = [list(map(int, input().split())) for i in range(N)]

def length(x, y, x1, y1):
	return math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
l = permutations(s)
ans = 0
for i in l:
	for j in range(1, N):
		ans += length(i[j - 1][0], i[j - 1][1], i[j][0], i[j][1])
print(ans / math.factorial(N))


import itertools
n = int(input())
a = [list(map(int, input().split(' '))) for i in range(n)]
ans = 0
for ([ix, iy], [jx, jy]) in itertools.combinations(a, 2):
	ans += ((jx - ix) ** 2 + (jy - iy) ** 2) ** 0.5 * 2
print(ans / n)


from itertools import permutations
import math
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
p = list(permutations(range(n), n))
ans = 0
for i in p:
	for j in range(n - 1):
		ans += ((l[i[j + 1]][0] - l[i[j]][0]) ** 2 + (l[i[j + 1]][1] - l[i[j]][1]) ** 2) ** 0.5
print(ans / math.factorial(n))


from itertools import permutations
from math import sqrt, factorial
n = int(input())
positions = [list(map(int, input().split())) for _ in range(n)]
perm = permutations(positions, n)
s = 0
for p in perm:
	for e in range(len(p) - 1):
		(xi, yi) = p[e]
		(xj, yj) = p[e + 1]
		s += sqrt((xj - xi) ** 2 + (yj - yi) ** 2)
print(s / factorial(n))


import itertools
import math
N = int(input())
A = []
b = []
count = 0
nums = [i for i in range(N)]
for balls in itertools.permutations(nums):
	b.append(list(balls))
for i in range(N):
	A.append(list(map(int, input().split())))
for j in range(N - 1):
	for i in b:
		count += math.sqrt(pow(A[i[j]][0] - A[i[j + 1]][0], 2) + pow(A[i[j]][1] - A[i[j + 1]][1], 2))
print(count / math.factorial(N))


import itertools
import math

def calc_kyori(a, b):
	return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
N = int(input())
l = []
for _ in range(N):
	tmp = list(map(int, input().split()))
	l.append(tmp)
total = 0
comb = 0
for i in list(itertools.permutations(list(range(N)))):
	comb += 1
	for j in range(N - 1):
		total += calc_kyori(l[i[j]], l[i[j + 1]])
print(total / comb)


from itertools import permutations
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
ans = 0
p = list(permutations(range(n), n))
for L in p:
	s = L[0]
	for i in L[1:]:
		ans += ((l[s][0] - l[i][0]) ** 2 + (l[s][1] - l[i][1]) ** 2) ** 0.5
		s = i
print(ans / len(p))


import sys
read = sys.stdin.read
from itertools import permutations
from math import factorial

def main():
	n = int(input())
	xy = [tuple(map(int, input().split())) for _ in range(n)]
	xydis = [[0] * n for _ in range(n)]
	for i1 in range(n):
		for i2 in range(n):
			xydis[i1][i2] = ((xy[i1][0] - xy[i2][0]) ** 2 + (xy[i1][1] - xy[i2][1]) ** 2) ** 0.5
	per = tuple(permutations(range(n), n))
	dis_sum = 0
	for pere in per:
		for j1 in range(n - 1):
			dis_sum += xydis[pere[j1]][pere[j1 + 1]]
	ans = dis_sum / factorial(n)
	print(ans)

def __starting_point():
	main()
__starting_point()


import math
n = int(input())
a = []
b = []
ans = 0

def z(p, q, r, s):
	return ((p - r) ** 2 + (q - s) ** 2) ** 0.5
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
for i in range(n):
	for j in range(i + 1, n):
		ans += 2 * z(a[i], b[i], a[j], b[j])
ans /= n
print(ans)


import itertools
n = int(input())
p = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
	(p[i][0], p[i][1]) = list(map(int, input().split()))

def dis(a, b):
	dis = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
	return dis ** (1 / 2)
perm = [i for i in range(n)]
total = 0
num = 0
for v in itertools.permutations(perm, n):
	path = 0
	for i in range(n - 1):
		path += dis(p[v[i]], p[v[i + 1]])
	num += 1
	total += path
print(total / num)


import itertools
import math
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
(x, y) = [list(i) for i in zip(*xy)]
l = []
for i in range(0, N):
	l.append(i)
p = list(itertools.permutations(l, N))
z = 0
for j in range(0, len(p)):
	for k in range(0, N - 1):
		z = z + math.sqrt(pow(x[p[j][k]] - x[p[j][k + 1]], 2) + pow(y[p[j][k]] - y[p[j][k + 1]], 2))
ans = z / len(p)
print(ans)


import itertools
import math
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
size = math.factorial(n)
a = list(itertools.permutations(l, n))
total = 0
for i in range(size):
	for j in range(n - 1):
		x1 = a[i][j][0]
		x2 = a[i][j + 1][0]
		y1 = a[i][j][1]
		y2 = a[i][j + 1][1]
		x_total = (x1 - x2) ** 2
		y_total = (y1 - y2) ** 2
		total += (x_total + y_total) ** 0.5
print(total / size)


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
sum = 0
for i in range(n):
	for j in range(i + 1, n):
		sum += ((a[i][0] - a[j][0]) ** 2 + (a[i][1] - a[j][1]) ** 2) ** 0.5
print(2 * sum / n)


n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
import math
d = []
for i in range(n):
	for j in range(n):
		if i != j:
			(x1, y1) = x_y[i]
			(x2, y2) = x_y[j]
			d.append(math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2))
print(sum(d) / n)


from itertools import permutations
N = int(input())
arr = [list(map(int, input().split())) for i in range(N)]

def dis(x):
	c = 0
	for i in range(N - 1):
		aa = arr[x[i]][0] - arr[x[i + 1]][0]
		bb = arr[x[i]][1] - arr[x[i + 1]][1]
		c += (aa ** 2 + bb ** 2) ** 0.5
	return c
count = 0
ans = 0
for i in permutations(list(range(0, N)), N):
	count += 1
	ans += dis(i)
print(ans / count)


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

def distance(i, j):
	(xi, yi) = xy[i]
	(xj, yj) = xy[j]
	return (xi - xj) ** 2 + (yi - yj) ** 2
visited = [False] * n
ans = 0

def dfs(route, length):
	nonlocal ans
	if len(route) == n:
		ans += length
		return
	else:
		for i in range(n):
			if visited[i]:
				continue
			next_distance = distance(route[-1], i) ** 0.5
			visited[i] = True
			dfs(route + [i], length + next_distance)
			visited[i] = False
cnt = 1
for i in range(n):
	cnt *= i + 1
	visited[i] = True
	dfs([i], 0)
	visited[i] = False
print(ans / cnt)


import itertools
import math
N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
	(x_list[i], y_list[i]) = map(int, input().split())
l_sum = 0
l = 0
for comb in itertools.combinations(range(N), 2):
	l = ((x_list[comb[0]] - x_list[comb[1]]) ** 2 + (y_list[comb[0]] - y_list[comb[1]]) ** 2) ** 0.5
	l_sum += l
ans = 2 * l_sum / N
print(ans)


import itertools
import math

def average_length():
	N = int(input())
	x = list()
	y = list()
	for _ in range(N):
		(X, Y) = map(int, input().split())
		x.append(X)
		y.append(Y)
	permutations_list = itertools.permutations([x for x in range(N)])
	all_case_distance_sum = 0
	for one_case in permutations_list:
		distance_sum = 0
		count = 0
		for i in one_case:
			count += 1
			if count == 1:
				pass
			else:
				D = (x[pass_num] - x[i]) ** 2 + (y[pass_num] - y[i]) ** 2
				d = math.sqrt(D)
				distance_sum += d
			pass_num = i
		all_case_distance_sum += distance_sum
	return all_case_distance_sum / math.factorial(N)
result = average_length()
print(result)


import functools
import itertools
import math
n = int(input())
poss = []
for _ in range(n):
	(x, y) = map(int, input().split())
	poss.append((x, y))

def dist(i, j):
	(xi, yi) = poss[i]
	(xj, yj) = poss[j]
	return math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
totaldist = 0.0
for order in itertools.permutations(range(n)):
	for i in range(1, n):
		totaldist += dist(order[i - 1], order[i])
totaldist /= functools.reduce(lambda x, y: x * y, range(1, n + 1))
print(totaldist)


import math, itertools
n = int(input())
X = list((list(map(int, input().split())) for _ in range(n)))
L = list(itertools.permutations(range(n), n))
ans = 0
for l in L:
	dist = 0
	for i in range(n - 1):
		(s, t) = (l[i], l[i + 1])
		vx = X[s][0] - X[t][0]
		vy = X[s][1] - X[t][1]
		dist += math.sqrt(vx ** 2 + vy ** 2)
	ans += dist
print(ans / len(L))


from math import sqrt
from itertools import permutations

def main():
	N = int(input())
	ans = 0.0
	P = [i for i in range(N)]
	C = [list(map(int, input().split())) for _ in range(N)]
	for p in permutations(P):
		for i in range(N - 1):
			ans += sqrt((C[p[i + 1]][0] - C[p[i]][0]) ** 2 + (C[p[i + 1]][1] - C[p[i]][1]) ** 2)
	for i in range(2, N + 1):
		ans /= i
	print(ans)

def __starting_point():
	main()
__starting_point()


from itertools import permutations
import math

def main():
	N = int(input())
	p = []
	for i in range(N):
		p.append(list(map(int, input().split())))
	c = 0
	tot = 0
	for points in permutations(p):
		d = 0
		for i in range(1, len(points)):
			d += dist(points[i - 1], points[i])
		c += 1
		tot += d
	print(tot / c)

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

def __starting_point():
	main()
__starting_point()


import itertools
N = int(input())
L = []
for i in range(N):
	(x, y) = map(int, input().split())
	L.append([x, y])
cnt = 0
total = 0
for v in itertools.permutations(L):
	for i in range(N - 1):
		x_1 = v[i][0]
		y_1 = v[i][1]
		x_2 = v[i + 1][0]
		y_2 = v[i + 1][1]
		total += ((x_2 - x_1) ** 2 + (y_2 - y_1) ** 2) ** 0.5
	cnt += 1
print(total / cnt)


import math
n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		disx = XY[i][0] - XY[j][0]
		disy = XY[i][1] - XY[j][1]
		dis = math.sqrt(disx ** 2 + disy ** 2)
		ans += dis
print(2 * ans / n)