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



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
xy = []
for i in range(n):
  x, y = map(int, input().split())
  xy.append((x, y))
np = len(list(permutations(range(n))))
dd = 0
for perm in permutations(range(n)):
  for i in range(n-1):
    dd += ((xy[perm[i-1]][0] - xy[perm[i]][0]) ** 2 + (xy[perm[i-1]][1] - xy[perm[i]][1]) ** 2) ** 0.5
print(dd/np)

Submission status: Accepted

Solution code:
from math import sqrt, factorial
from itertools import permutations

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
distance = {}
for i in range(N):
    for j in range(N):
        if i!=j:
            distance[str(i)+str(j)] = sqrt((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)
ans = 0

for S in list(permutations([i for i in range(N)], N)):
    for i in range(N-1):
        key = str(S[i]) + str(S[i+1])
        ans += distance[key]
print(ans/factorial(N))

Submission status: Accepted

Solution code:
import math
from itertools import permutations

def solve():
    n = int(input())
    cord = [list(map(int, input().split())) for _ in range(n)]
    # print(cord)
    # dist = {}
    # for i in range(n):
    #     for j in range(n):
    #         if i == j: continue
    #         d = math.sqrt(pow(cord[i][0] - cord[j][0], 2) + pow(cord[i][1] - cord[j][1], 2))
    #         dist[(i, j)] = d
    # print(dist)
    sm = 0
    for cnt, i in enumerate(permutations(range(n))):
        # print(i)
        for j in range(1, n):
            # print('aaa', i[j-1], i[j])
            # d = dist[(i[j-1], i[j])]
            s = i[j-1]
            t = i[j]
            d = math.sqrt(pow(cord[s][0] - cord[t][0], 2) + pow(cord[s][1] - cord[t][1], 2))
            # print(d)
            sm = sm + d
    print(sm / (cnt+1))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
from itertools import permutations

def solve():
    n = int(input())
    cord = [list(map(int, input().split())) for _ in range(n)]
    # print(cord)
    dist = {}
    for i in range(n):
        for j in range(n):
            if i == j: continue
            d = math.sqrt(pow(cord[i][0] - cord[j][0], 2) + pow(cord[i][1] - cord[j][1], 2))
            dist[(i, j)] = d
    # print(dist)
    sm = 0
    for cnt, i in enumerate(permutations(range(n))):
        # print(i)
        for j in range(1, n):
            # print('aaa', i[j-1], i[j])
            d = dist[(i[j-1], i[j])]
            # print(d)
            sm = sm + d
    print(sm / (cnt+1))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools

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

l = list(range(n))
cl = []
for i in itertools.permutations(l):
  cl.append(i)
# print(cl[0][1])
total = 0
N = len(cl)
for i in range(N):
  for j in range(1,n):
    now = cl[i][j]
    past = cl[i][j-1]
    total += ((xy[now][0] - xy[past][0])**2+(xy[now][1] - xy[past][1])**2)**0.5
print(total/N)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 145
# C - Average Length
# https://atcoder.jp/contests/abc145/tasks/abc145_c
from itertools import permutations

N, *A = map(int, open(0).read().split())
X = A[0::2]
Y = A[1::2]

def distance(a, b):
    return ((X[a]-X[b])**2 + (Y[a]-Y[b])**2)**0.5


length = 0
cnt = 0
for P in permutations(range(N)):
    cnt += 1
    prev = P[0]
    for i in P[1:]:
        length += distance(prev, i)
        prev = i

print(length/cnt)

Submission status: Accepted

Solution code:
import itertools
import math

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

def factorial(a):
  if (a == 1):
    return 1
  return a * factorial(a-1)

f = factorial(s)

length = 0
p = itertools.permutations(m, r=None)
for c in p:
  l = list(c)
  for k in range(len(l) - 1):
    length += math.sqrt((l[k+1][0] - l[k][0] ) ** 2 + (l[k+1][1] - l[k][1]) ** 2)

print(length / f)

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
lis=[]
for i in range(N):
	[x,y]=[int(j)+1000 for j in input().split()]
	lis+=[x+y*10000]
A=list(itertools.permutations(lis))
add=0
cnt=0
for i in range(len(A)):
	for j in range(len(A[i])-1):
		add+=(((A[i][j]//10000)-(A[i][j+1]//10000))**2+((A[i][j]%10000)-(A[i][j+1]%10000))**2)**0.5
		cnt+=1
print(add/math.factorial(N))

Submission status: Accepted

Solution code:
N = int(input())
P = [list(map(int,input().split())) for i in range(N)]

from itertools import permutations, combinations,combinations_with_replacement,product

arr = list(permutations(P))

ans = 0

for p in arr:
    l = 0
    for (x1, y1), (x2, y2) in zip (p, p[1:]):
        l += ((x1-x2)**2 + (y1-y2)**2)**0.5
    ans += l

print(ans/len(arr))

Submission status: Accepted

Solution code:
import math

n = int(input())

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

s = 0
for i in range(n):
    x1, y1 = p[i]
    for j in range(n):
        x2, y2 = p[j]

        s += math.sqrt((x1-x2)**2 + (y1-y2)**2)

print(s/n)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
XY=[]
for _ in range(N):
    tmp=list(map(int,input().split()))
    XY.append(tmp)
l=[i for i in range(N)]
permutation = itertools.permutations(l, 2)
total=0
for p in permutation:
    i=p[0]
    j=p[1]
    total+=((XY[i][0] - XY[j][0])**2 + (XY[i][1] - XY[j][1])**2)**0.5

print(total/N)

Submission status: Accepted

Solution code:
import math

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

sum_dist = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum_dist += math.sqrt((xs[i]-xs[j]) ** 2 + (ys[i]-ys[j]) ** 2)

print(sum_dist * 2 / n)

Submission status: Accepted

Solution code:
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):
        x1,y1 = xy[i]
        x2,y2 = xy[j]
        ans += ((x2-x1)**2 + (y2-y1)**2)**(1/2)

print(ans*(2/n))

Submission status: Accepted

Solution code:
from math import sqrt, factorial
from itertools import permutations as pe
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
l = [i for i in range(N)]
d = 0
for i in pe(l):
    flag = False
    dd = 0
    x, y, xx, yy = 0, 0, 0, 0
    
    for ii in i:
        if flag:
            xx, yy = X[ii][0], X[ii][1]
            dd += sqrt((x-xx)**2+(y-yy)**2)
            flag=False
        x, y = X[ii][0], X[ii][1]
        flag=True
    d+=dd
print(d/factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from math import factorial
from math import sqrt
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

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())


#ここから書き始める
n = int(input())
a = []
for i in range(n):
    x, y = map(int, input().split())
    a.append([x, y])
total = 0
for i in permutations(a):
    # print(i)
    for j in range(1, n):
        x_distance = i[j][0] - i[j - 1][0]
        y_distance = i[j][1] - i[j - 1][1]
        d = sqrt(x_distance ** 2 + y_distance ** 2)
        total += d
ans = total / factorial(n)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

cnt=0
ans=0.0
for p in permutations(range(N)):
    cnt+=1
    for i in range(N-1):
        dx=pts[p[i+1]][0]-pts[p[i]][0]
        dy=pts[p[i+1]][1]-pts[p[i]][1]

        ans+=math.sqrt(dx**2+dy**2)

print(ans/cnt)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i] = map(int,input().split())
num=[i for i in range(n)]
def dist(i,j):
    return ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
ans=0
s=0
for perm in list(itertools.permutations(num)):
    for i in range(n-1):
        ans+=dist(perm[i],perm[i+1])
    s+=1     
print(ans/s)

Submission status: Accepted

Solution code:
from math import sqrt, factorial
from itertools import permutations
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
order = [i for i in range(N)]
s = 0
for a in permutations(order, N):
    for b in range(N-1):
        s += sqrt((xy[a[b]][0]-xy[a[b+1]][0])**2+(xy[a[b]][1]-xy[a[b+1]][1])**2)
print(s/factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations

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


def dist(i, j):
    return ((towns[i][0] - towns[j][0])**2 +
            (towns[i][1] - towns[j][1])**2)**0.5


ans = cnt = 0
for perm in permutations(range(n)):
    cand = 0
    for i in range(n - 1):
        cand += dist(perm[i], perm[i + 1])
    ans += cand
    cnt += 1

ans /= cnt
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, fsum
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

ds = []
n = 0
for rt in permutations(towns, N):
    for i in range(1, N):
        x1, y1 = rt[i-1]
        x2, y2 = rt[i]
        d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        ds.append(d)
    n += 1
ans = fsum(ds) / n
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
import numpy as np

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

dist = 0
for order in itertools.permutations(range(N), N):
    for i in range(1, len(order)):
        dist += np.sqrt((X[order[i]] - X[order[i - 1]])**2 +
                        (Y[order[i]] - Y[order[i - 1]])**2)
ans = dist / math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
xy = [[int(j) for j in input().split()] for i in range(n)]
x = [i[0] for i in xy]
y = [i[1] for i in xy]
sum = 0
ps = list(itertools.permutations(range(n), n))
for i in ps:
    for j in range(len(i)-1):
        tmp = math.sqrt((x[i[j]] - x[i[j+1]]) ** 2 + (y[i[j]] - y[i[j+1]]) ** 2)
        sum += tmp
print(sum / len(ps))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline
def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
#import numpy as np

from itertools import permutations
from math import factorial

def main():
	n=II()
	li=[TI() for _ in range(n)]
	ans=0
	for p in permutations(range(n),n):
		tmp=0
		px=py=1001
		for i in p:
			x,y=li[i][0],li[i][1]
			if px==1001:
				px,py=x,y
			else:
				tmp+=((px-x)**2+(py-y)**2)**0.5
				px,py=x,y
		ans+=tmp

	ans/=factorial(n)
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math

n = int(input())

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

distance_sum = 0
for i in range(n):
    for j in range(i+1, n):
        distance_sum += math.sqrt((coords[i][0] - coords[j][0])**2 + (coords[i][1] - coords[j][1])**2)

print(distance_sum * (n-1) / (n * (n-1) // 2) )
# 完全グラフの変数は n * (n-1) // 2, うち1回の経路で使うのはn-1本。
# 約分して以下のようにもできる；
# print(distance_sum * 2 / n)

Submission status: Accepted

Solution code:
import math
n=int(input())
xy=[input().split(" ") for i in range(n)]
#print(xy)
l=0
for i in range(n):
    for j in range(n):
        l+=math.sqrt((int(xy[i][0])-int(xy[j][0]))**2+(int(xy[i][1])-int(xy[j][1]))**2)
        #print(l)
print(l/n)

Submission status: Accepted

Solution code:
import sys
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

town = [list(map(int, input().split())) for _ in range(N)]
lis = [x for x in range(N)]
roots = list(itertools.permutations(lis))
sum_dis = 0

for i in range(len(roots)):
    for j in range(N-1):
        sum_dis += math.sqrt((town[roots[i][j]][0] - town[roots[i][j+1]][0])**2 + (town[roots[i][j]][1] - town[roots[i][j+1]][1])**2)

print(sum_dis / len(roots))

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = [int(n) for n in input().split()]
    X.append(x)
    Y.append(y)
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += ((X[j]-X[i])**2 + (Y[j]-Y[i])**2)**0.5
print(ans*2/N)

Submission status: Accepted

Solution code:
n = int(input())
X = []
Y = []
for i in range(n):
  x, y = map(int, input(). split())
  X.append(x)
  Y.append(y)
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=( (X[j]-X[i])**2 + (Y[j]-Y[i])**2 )**(1/2)
print(2*ans/n)

Submission status: Accepted

Solution code:
import fractions
import math
import itertools

def distance_measure(n,*args):
    distance_x = 0
    distance_y = 0
    distance_xy = 0
    distance = 0
    for i in range(n-1):
   
        distance_x = (args[0][i+1][0]-args[0][i][0])**2
        distance_y = (args[0][i+1][1]-args[0][i][1])**2
        distance_xy += math.sqrt(distance_x+distance_y)
    distance += distance_xy 
   # print(distance)
    return distance
    


if __name__ =="__main__":
    n = int(input())
    all_dist = 0
    #g = list([0] * n for _ in range(n))
    g = [0]*n
    for i in range (n):
        x,y = map(int,input().split())
        g[i] = x,y
    #print(g)
    #print(g[1][0])
    for i in itertools.permutations(g,n):
        #print(i)
        distance = distance_measure(n,i)
        all_dist += distance

    ave_dist = all_dist/math.factorial(n)
    print(ave_dist)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
p = []
for _ in range(n):
    p.append(list(map(int, input().split())))
dis = 0
for i, j in combinations([i for i in range(n)], 2):
    dis += ((p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2)**(1/2)
print(dis/n*2)

Submission status: Accepted

Solution code:
from itertools import permutations


def dist(points,a,b):
    x = ((points[a][0]-points[b][0])**2+(points[a][1]-points[b][1])**2)**0.5
    return x

def resolve():
    N = int(input())

    points = [ [int(j) for j in input().split()]  for i in range(N)]
    score =0
    count =0
    for route in permutations(range(N),N):
        
        for a,b in zip(route,route[1:]):
            score += dist(points,a,b)

        count +=1

    print(score/count)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import math

n = int(input())
corrdinate = []
[corrdinate.append(list(map(int,input().split()))) for _ in range(n)]

total = 0
factorial = 1
for i in range(n):
    factorial *= n-i

fa = factorial / ((n))
for i in range(n):
    for j in range(i+1,n):
        xi = corrdinate[i][0]
        xj = corrdinate[j][0]
        yi = corrdinate[i][1]
        yj = corrdinate[j][1]
        total += math.sqrt( (xi - xj)**2 + (yi - yj)**2 ) * 2 * fa

print(total / (factorial ) )

Submission status: Accepted

Solution code:
n = int(input())
lis = []
for i in range(n):
    lis.append(list(map(int, input().split())))
s = 0
for i in range(n):
    for j in range(i,n):
        s += ((lis[i][0] - lis[j][0])**2 + (lis[i][1] - lis[j][1])**2)**(1/2)
print(s*2/n)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
lis1 = []
for i in range(n):
    lis1.append(list(map(int, input().split())))
S = 0
for i in list(itertools.permutations(range(n))):
    for j in range(n-1):
        S += math.sqrt((lis1[i[j]][0]-lis1[i[j+1]][0])**2 + (lis1[i[j]][1]-lis1[i[j+1]][1])**2)
for i in range(1, n+1):
    S = S / i
print(S)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools
from math import sqrt

n = int(readline())
xy = [list(map(int, readline().split())) for i in range(n)]
memo = [i for i in range(n)]
z = list(itertools.permutations(memo))
ans = 0
for i in range(len(z)):
    for j in range(n - 1):
        ans += sqrt((xy[z[i][j]][0] - xy[z[i][j + 1]][0]) ** 2 + (xy[z[i][j]][1] - xy[z[i][j + 1]][1]) ** 2)
print(ans / len(z))

Submission status: Accepted

Solution code:
import math
N = int(input())
xi = []
yi = []

for i in range(N):
  x, y = map(int, input(). split())
  xi.append(x)
  yi.append(y)

L=0

for j in range(N):
  for k in range(N):
    if j >= k:
      continue
    L += math.sqrt((xi[j]-xi[k])**2 + (yi[j]-yi[k])**2)
    
print(2*L/N)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial, log, log10, log2
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
from datetime import datetime as dt

def main():
  n = int(readline())
  x = [0] *n
  y = [0]*n
  for i in range(n):
    x[i], y[i] = map(int, readline().split())
  dis = [[0 for i in range(n)]for j in range(n)]
  total = 0
  for i in range(n):
    for j in range(i+1,n):
      total += 2*((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
  print(total/n)
  
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i],Y[i] = map(int,input().split())

import math
length = 0
for i in range(N-1):
    for j in range(i+1,N):
        length += math.sqrt((X[i]-X[j])**2+(Y[i]-Y[j])**2)

C = N*(N-1)/2

print((N-1)*length/C)

Submission status: Accepted

Solution code:
import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
X = []
Y = []

for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)

def distance(i,j):
    return math.sqrt((X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]))

distance_sum = 0

for i in range(N):
    for j in range(N):
        distance_sum += distance(i,j)

print(distance_sum/N)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

ans = 0
for perm in itertools.permutations(range(N)):
    for i in range(0, N - 1):
        ans += math.sqrt((x[perm[i]] - x[perm[i + 1]]) ** 2 + (y[perm[i]] - y[perm[i + 1]]) ** 2)

print(ans / fact(N))

Submission status: Accepted

Solution code:
import math
import itertools
N=int(input())
K=[list(map(int,input().split())) for i in range(N)]
point = list(range(N))

#distance of all edges
dist_list = []
for v in itertools.combinations(point,2):
    dist = math.sqrt((K[v[0]][0] - K[v[1]][0])**2 + (K[v[0]][1] - K[v[1]][1])**2)
    dist_list.append([list(v),dist])

sum = 0
for v in itertools.permutations(point,N):
    for i in range(N-1):
        p1,p2 = v[i],v[i+1]

        for item in dist_list:
            if [p1,p2] in item or [p2,p1] in item:
                sum += item[1]
                break
        

ans = sum / math.factorial(N)

print(ans)

Submission status: Accepted

Solution code:
import math
N=int(input())
x=[0]*N
y=[0]*N
for i in range(N):
    x[i],y[i]=map(int,input().split())
ans_sum=0
for i in range(N):
    for j in range(N):
            ans_sum+=math.sqrt((x[j]-x[i])**2+(y[j]-y[i])**2)
print(ans_sum/N)

Submission status: Accepted

Solution code:
import math
def distance(x1,x2,y1,y2):
  d=math.sqrt((x1-x2)**2+(y1-y2)**2)
  return d

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

list=[]
for i in range(n):
  for j in range(n):
    k=distance(zahyou[i][0],zahyou[j][0],zahyou[i][1],zahyou[j][1])
    list.append(k)

s=sum(list)/n
print(s)

Submission status: Accepted

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

xi=[]
yi=[]

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

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

print(l*2/n)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
import math

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

    ans = []
    def dfs(d, perm):
        if d==N:
            dist = 0
            for i in range(N-1):
                dist += ((xy[perm[i+1]][0]-xy[perm[i]][0])**2+(xy[perm[i+1]][1]-xy[perm[i]][1])**2)**0.5
            ans.append(dist)
        else:
            for i in range(N):
                if i not in perm:
                    dfs(d+1, perm+[i])

    dfs(0, [])
    print(sum(ans)/math.factorial(N))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    ans = [0]
    p = 1
    for i in range(N):
        p *= i+1
    def dfs(d, perm):
        if d==N:
            dist = 0
            for i in range(N-1):
                dist += ((xy[perm[i+1]][0]-xy[perm[i]][0])**2+(xy[perm[i+1]][1]-xy[perm[i]][1])**2)**0.5
            ans[0] += dist
        else:
            for i in range(N):
                if i not in perm:
                    dfs(d+1, perm+[i])

    dfs(0, [])
    print(ans[0]/p)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
import numpy as np
from itertools import permutations
n = int(input())
XY = list(tuple(map(int, input().split())) for _ in range(n))

dist = 0
for per in permutations(range(n)):
    for origin, next in zip(per, per[1:]):
        x1, y1 = XY[origin][0], XY[origin][1]
        x2, y2 = XY[next][0], XY[next][1]

        dist += np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
print(dist / math.factorial(n))

Submission status: Accepted

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

N = int(input())

city = []
l = [i for i in range(N)]
for i in range(1,N+1):
  x,y = map(int,input().split())
  city.append([x,y])
  
l = list(itertools.permutations(l))
sum_dis = [0]*len(l)
for i in range(len(l)):
  for j in range(N-1):
    sum_dis[i]+=getdis(city[l[i][j]],city[l[i][j+1]])
print(sum(sum_dis)/len(l))

Submission status: Accepted

Solution code:
x = int(input())
a = [list(map(int,input().split())) for i in range(x)]
ans = 0
for i in range(x):
    for j in range(x):
        if i!=j:
            ans += ((abs(a[i][0]-a[j][0])**2+abs(a[i][1]-a[j][1])**2))**0.5
print(ans/x)

Submission status: Accepted

Solution code:
x = int(input())
a = [list(map(int,input().split(" "))) for i in range(x)]
ans = 0
for i in range(x):
    for j in range(x):
        if i!=j:
            ans += ((abs(a[i][0]-a[j][0])**2+abs(a[i][1]-a[j][1])**2))**0.5
print(ans/x)

Submission status: Accepted

Solution code:
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
ans=0
for x1,y1 in xy:
    for x2,y2 in xy:
        ans+=((x2-x1)**2+(y2-y1)**2)**0.5
print(ans/N)

Submission status: Accepted

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

total = 0
for i in range(N-1):
    for j in range(i+1,N):
        total += ((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
        
        
n = 2/N
ans = total*n
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
R = np.array([list(map(int,input().split())) for i in range(N)])
print(sum(np.linalg.norm(i-j) for i in R for j in R)/N)

Submission status: Accepted

Solution code:
N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
sum=0
kaijyo=1
for i in  range(N):
  for j in range(N):
    if i!=j:
      sum+=((XY[i][0]-XY[j][0])**2+(XY[i][1]-XY[j][1])**2)**0.5
    else:
      continue
print(sum/N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math
n=int(input())
l=[]
l1=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
N=math.factorial(n)
c=itertools.permutations(l,n)
l=list(c)
for j in range(N):
    for k in range(n-1):
        d=math.sqrt((l[j][k][0]-l[j][k+1][0])**2+(l[j][k][1]-l[j][k+1][1])**2)
        l1.append(d)
print(sum(l1)/N)

Submission status: Accepted

Solution code:
import itertools
import math
import statistics
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]


def cal(list, n):
    ret = 0
    for i in range(n-1):
        ret += math.sqrt(((list[i][0]-list[i+1][0])**2)+((list[i][1]-list[i+1][1])**2))
    return(ret)


ans = []
for l in list(itertools.permutations(xy)):
    ans.append(cal(l, N))
print(statistics.mean(ans))

Submission status: Accepted

Solution code:
#C
import math
n = int(input())
coordinate = []
for _ in range(n):
    x,y = map(int,input().split())
    coordinate.append([x,y])
dist = 0
def culc_dist(x1,y1,x2,y2):
    return (math.sqrt((x1-x2)**2 + (y1-y2)**2))
    
for i in range(n):
    for j in range(n):
        if i != j:
            dist += culc_dist(coordinate[i][0],coordinate[i][1],coordinate[j][0],coordinate[j][1])
dist /= n

print(dist)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations

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


def get_dist(ax,ay, bx, by):
    return sqrt((ax-bx)**2 + (ay-by)**2)

dist_matrix = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        dist_matrix[i][j] = get_dist(xy[i][0], xy[i][1], xy[j][0], xy[j][1])

perm = permutations(list(range(N)), N)
n = 0
paths = []
for v in perm:
    n += 1
    one_path = []
    for k in range(len(v)-1):
        one_path.append([v[k], v[k+1]])
    paths.append(one_path)

d_sum = 0
for p in paths:
    for q in p:
        d_sum += dist_matrix[q[0]][q[1]]

print(d_sum/n)

Submission status: Accepted

Solution code:
import math
import itertools

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

x = 0
y = 1
d = 0

for p in itertools.permutations(range(n)):
    p = list(p)
    for i in range(n-1):
        d += ((xy[p[i]][x] - xy[p[i+1]][x])**2 + (xy[p[i]][y] - xy[p[i+1]][y])**2)**0.5
        # print(d)

print(d/math.factorial(n))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import itertools

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

def d(x1, y1, x2, y2):
    x = abs(x1-x2)
    y = abs(y1-y2)
    return (x*x + y*y) ** 0.5

N = i_i()
xy = [i_l() for x in range(N)]
p = itertools.permutations(xy, N)
arr = list(p)

acc = 0
for a in arr:
    tmp = 0
    for i in range(N-1):
        tmp += d(a[i][0], a[i][1], a[i+1][0], a[i+1][1])
    acc += tmp
    tmp = 0

print(acc/ len(arr))

Submission status: Accepted

Solution code:
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(itertools.permutations([i for i in range(1, N+1)]))

n = math.factorial(N)
road = 0
for i in range(n):
    for j in range(N-1):
        road += math.sqrt((x[a[i][j]-1]-x[a[i][j+1]-1])**2+(y[a[i][j]-1]-y[a[i][j+1]-1])**2)
print(road/n)

Submission status: Accepted

Solution code:
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
ans=0
for x1,y1 in xy:
    for x2,y2 in xy:
        ans+=((x2-x1)**2+(y2-y1)**2)**0.5
print(ans/N)