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:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n):
  for j in range(n):
    ans+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
print(ans/n)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial
n = int(input())
patern = factorial(n)
town = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for rute in permutations(range(n)):
    road = 0
    for i in range(n-1):
        x,y = town[rute[i]]
        nx,ny = town[rute[i+1]]
        road += ((x-nx)**2 + (y-ny)**2)**(1/2)
    ans += road
print(ans/patern)

Submission status: Accepted

Solution code:
def dist(i, j):
    dx = x[i] - x[j]
    dy = y[i] - y[j]
    return pow(dx * dx + dy * dy, 0.5)


xys = []
x = []
y = []

n = int(raw_input())

for _ in range(n):
    xys.append(map(int, raw_input().split()))

for xy in xys:
    x.append(xy[0])
    y.append(xy[1])

result = 0.0

for i in range(n):
    for j in range(i, n):
        result += (dist(i, j)) * 2 / n

print(result)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc145/tasks/abc145_c
import math
import copy

N = int(input())
x_y_list = []

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


visited = [False] * N
d_list = []
log_list = []

def dfs(distance, ex_coord, log):

    if all(visited):
        d_list.append(distance)
        log_list.append(copy.copy(log))

        return

    for i in range(N):
        if visited[i]:
            continue
        else:
            tmp = 0
            if ex_coord != []:
                tmp = (ex_coord[0] - x_y_list[i][0]) ** 2 + (ex_coord[1] - x_y_list[i][1]) ** 2
                tmp = math.sqrt(tmp)
                distance += tmp

            visited[i] = True
            log.append(i + 1)
            dfs(distance, x_y_list[i], log)
            del log[-1]
            visited[i] = False
            distance -= tmp

log_tmp = []
dfs(0, [], log_tmp)
print(sum(d_list) / len(d_list))

Submission status: Accepted

Solution code:
import itertools,math
n=int(input())
t=[list(map(int,input().split())) for i in range(n)]
s=[i for i in range(n)]
l=list(itertools.permutations(s))
tmp=[]
for i in l:
    dis=0
    for j in range(n-1):
        x1=t[i[j+1]][0]
        x2=t[i[j]][0]
        y1=t[i[j+1]][1]
        y2=t[i[j]][1]
        dis+=((x2-x1)**2+(y2-y1)**2)**(1/2)
    tmp.append(dis)
print(sum(tmp)/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

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

distance = 0
for v in itertools.permutations(index):
    for i in range(n-1):
        distance += math.sqrt((x[v[i]] - x[v[i+1]]) **
                              2 + (y[v[i]]-y[v[i+1]])**2)


print(distance/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools

N = int(input())
N_list = [int(x) for x in range(N)]
com_N_list = list(itertools.permutations(N_list,N))


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

dis_list = []

for j in com_N_list:
    dis = 0
    for i in range(N-1,0,-1):
        dis += ((point_list[j[i]][0]-point_list[j[i-1]][0])**2 + (point_list[j[i]][1]-point_list[j[i-1]][1])**2)**(1/2)
    dis_list.append(dis)

ans = sum(dis_list)/(len(com_N_list))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

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

a = []

for i in range(1,N+1):
    a += [i]

b = []

for v in itertools.permutations(a, N):
    b.append(list(v))

ancerL = []

for i in range(len(b)):
    ancer = 0
    for j in range(N-1):
        
        combined1 = [x - y for (x, y) in zip(q[b[i][j+1]-1], q[b[i][j]-1])]
        
        ancer += math.sqrt(combined1[0]**2 + combined1[1]**2)
       
    ancerL.append(ancer)
    
print(sum(ancerL) / len(ancerL))

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
x = [0]*N
y = [0]*N
route = list(permutations(range(N)))

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

ans = 0
for r in route:
    for l in range(len(r)-1):
        tmp = ((x[r[l]] - x[r[l+1]])**2 + (y[r[l]] - y[r[l+1]])**2)**0.5
        ans += tmp

print(ans / len(route))

Submission status: Accepted

Solution code:
import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
sm = 0
for p in P:
    for i,j in zip(p,p[1:]):
        xi,yi = zahyo[i]
        xj,yj = zahyo[j]
        sm += (((xi-xj)**2+(yi-yj)**2)**0.5)
print(sm/len(P))

Submission status: Accepted

Solution code:
N = int(input())
towns = list()
flag = [False for i in range(N)]


def factorial(n):
    if n < 1:
        return 1
    return n * factorial(n - 1)


def distance(x, y):
    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5


def dfs(n, prev_town):

    if n == N - 1:
        return 0

    res = 0

    for i, town in enumerate(towns):
        if flag[i] is False:
            flag[i] = True
            res += dfs(n + 1, town)
            res += distance(prev_town, town) * factorial(N - n - 2)
            flag[i] = False

    return res


for i in range(N):
    towns.append(tuple(map(int, input().split())))

ans = 0

for i, town in enumerate(towns):
    flag[i] = True
    ans += dfs(0, towns[i])
    flag[i] = False

ans = ans / factorial(N)

print(ans)

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)
 
sum = 0
for i in range(N):
    for j in range(N):
        x = (X[i] - X[j])**2
        y = (Y[i] - Y[j])**2
        sum += (x + y)**(1/2)

print(sum/N)

Submission status: Accepted

Solution code:
# C - Average Length

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

D = []
for i in range(N):
    for j in range(i + 1, N):
        dist = (((P[i][0] - P[j][0]) ** 2) +
                ((P[i][1] - P[j][1]) ** 2)) ** (1 / 2)
        D.append(dist)

print(sum(D) / len(D) * (N - 1))

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
l=[]
mem=[]
P=list(itertools.permutations(range(1,N+1)))
for i in range(N):
    l.append(list(map(int,input().split())))
for i in range(len(P)):
    mem.append(0)
    for j in range(len(P[i])-1):
        pos1 = P[i][j]-1
        pos2 = P[i][j+1]-1
        mem[i] += math.sqrt(((l[pos1][0]-l[pos2][0])**2) + ((l[pos1][1]-l[pos2][1])**2))
print(sum(mem)/len(mem))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
town = []
for _ in range(N):
  town.append(list(map(int, input().split())))
ind = [i for i in range(N)]
dis = 0
for ind in itertools.permutations(ind):
  for j in range(N):
    if j == N-1:
      break
    dis += ((town[ind[j]][0] - town[ind[j+1]][0])**2 + (town[ind[j]][1] - town[ind[j+1]][1])**2)**0.5
print(dis/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
lis = [x for x in range(n)]
permutations_lis = itertools.permutations(lis)
xy = [list(map(int,input().split())) for i in range(n)]
judge = []
for i in permutations_lis:
  count = 0
  first = i[0]
  for p in i:
    count += math.sqrt((xy[p][0]-xy[first][0])**2+(xy[p][1]-xy[first][1])**2)
    first = p
  else:
    judge.append(count)
print(sum(judge)/len(judge))

Submission status: Accepted

Solution code:
import itertools
N=int(input())
point=[]
for _ in range(N):
    x,y=map(int,input().split())
    point.append([x,y])
nums=[i for i in range(1,N+1)]
perm=list(itertools.permutations(nums,N))
dist=0

for pattern in perm:
    tmp_dist=0
    for i in range(N-1):
        tmp_dist+=((point[pattern[i]-1][0]-point[pattern[i+1]-1][0])**2+(point[pattern[i]-1][1]-point[pattern[i+1]-1][1])**2)**0.5
    dist+=tmp_dist
print(dist/len(perm))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')
from math import sqrt
from itertools import permutations
def solve():
    n = II()

    town = []
    for i in range(n):
        x, y = MI()
        town.append((x, y))

    def f(t1, t2):
        x1, y1 = t1
        x2, y2 = t2
        return sqrt( (x1 - x2) ** 2 + (y1 - y2) ** 2)

    tot = 0
    cnt = 0
    for t in permutations(town, n):
        cnt += 1
        d = 0
        # print(t)
        for i in range(n-1):
            j = i + 1
            d = f(t[i], t[j])
            # print(d)
            tot += d

    print(tot / cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

dst = 0
for i in range(n-1):
    for j in range(i+1, n):
        dst += ((pos[i][0]-pos[j][0])**2 + (pos[i][1]-pos[j][1])**2)**(1/2)
print(dst*2/n)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
XY = [[int(i) for i in input().split()] for j in range(N)]

All = list(itertools.permutations(range(N)))

def euqlid(a1,a2,b1,b2):
    return pow((a1-a2)**2+(b1-b2)**2,0.5)
    
ans = 0
co = 0
for i in All:
    count = 0
    i = list(i)
    x,y = XY[i[0]]
    for j in i[1:]:
        s,t = XY[j]
        count += euqlid(x,s,y,t)
        x,y = s,t
    ans += count
    co += 1

print(ans/co)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
xy_inputs = [[int(j) for j in input().split()]for i in range(n)]

dist_map = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        x1,y1 = map(int,xy_inputs[i])
        x2,y2 = map(int,xy_inputs[j])
        dist = ((x1-x2)**2+(y1-y2)**2)**0.5
        dist_map[i][j]=dist
        dist_map[j][i]=dist

ans=0
li = list(itertools.permutations([i for i in range(n)],n))
for l in li:
    for i in range(len(l)-1):
        ans+=dist_map[l[i]][l[i+1]]

print(ans/len(li))

Submission status: Accepted

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

summ=0
for i in range(0,n-1):
  for j in range(i+1,n):
    dis=((lis[i][0]-lis[j][0])**2+(lis[i][1]-lis[j][1])**2)**(1/2)
    summ+=dis
print(summ*2/n)

Submission status: Accepted

Solution code:
# C - Average Length

import itertools

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

def calcDist(Y):
    dist = 0
    for i in range(1, len(Y)):
        dist += pow(pow(P[Y[i]][0] - P[Y[i-1]][0], 2) + pow(P[Y[i]][1] - P[Y[i-1]][1], 2), 0.5)
    return dist

def dfs(X):
    global ans
    if len(X)==N:
        ans.append(calcDist(X))
        return
    for i in range(N):
        if i not in X:
            X.append(i)
            dfs(X)
            X.pop()

ans = []
X = []
#dfs(X)

for X in itertools.permutations(range(N),N):
    ans.append(calcDist(X))

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

Submission status: Accepted

Solution code:
# C - Average Length

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

def calcDist(Y):
    dist = 0
    for i in range(1, len(Y)):
        dist += pow(pow(P[Y[i]][0] - P[Y[i-1]][0], 2) + pow(P[Y[i]][1] - P[Y[i-1]][1], 2), 0.5)
    return dist

def dfs(X):
    global ans
    if len(X)==N:
        ans.append(calcDist(X))
        return
    for i in range(N):
        if i not in X:
            X.append(i)
            dfs(X)
            X.pop()

ans = []
X = []
dfs(X)

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

Submission status: Accepted

Solution code:
import math

n = int(input())
xyn = [None] * n
for i in range(n):
    xyn[i] = list(map(int, input().split(' ')))

t2t = []

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            dis = math.sqrt((xyn[i][0] - xyn[j][0]) ** 2 + (xyn[i][1] - xyn[j][1]) ** 2)
            t2t.append(dis)

ave = sum(t2t) / len(t2t) * (n - 1)

print(ave)

Submission status: Accepted

Solution code:
import math
import itertools
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
def distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

dist = 0
cnt = 0
for p in itertools.permutations(range(n)):
    for i in range(n-1):
        dist += distance(xy[p[i]][0], xy[p[i]][1], xy[p[i+1]][0], xy[p[i+1]][1])
    cnt += 1
ans = dist / cnt
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
num = list(list(map(int, input().split())) for i in range(n))

num = list(itertools.permutations(num))

count = 0

for i in num:
  for j in range(len(i) - 1):
    count += math.sqrt(((i[j][0] - i[j + 1][0]) ** 2 + (i[j][1] - i[j + 1][1]) ** 2))

print(count/math.factorial(n))

Submission status: Accepted

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

if n==2:
    print(((L[0][0]-L[1][0])**2+(L[0][1]-L[1][1])**2)**0.5)
else:
    s=0
    for p in range(n):
        for q in range(n):
            s+=((L[p][0]-L[q][0])**2+(L[p][1]-L[q][1])**2)**0.5
    print(s*((n-1)/(n*(n-1))))

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations
def main():
    n = int(input())
    town_coor = []
    for _ in range(n):
        town_coor.append(tuple(map(int, input().split())))

    dists = [[0]*n for _ in range(n)]
    for j1 in range(n):
        for j2 in range(n):
            dists[j1][j2] = ((town_coor[j1][0] - town_coor[j2][0])**2 + (town_coor[j1][1] - town_coor[j2][1])**2)**0.5


    towns = [i for i in range(n)]
    roads = permutations(towns, n)
    sum_roads = 0
    for road in roads:
        sum_road = 0
        for i1 in range(n-1):
            sum_road += dists[road[i1]][road[i1+1]]
        sum_roads += sum_road
    print(sum_roads / factorial(n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations
def main():
    n = int(input())
    town_coor = []
    for _ in range(n):
        town_coor.append(tuple(map(int, input().split())))

    towns = [i for i in range(n)]
    roads = permutations(towns, n)
    sum_roads = 0
    for road in roads:
        sum_road = 0
        for i1 in range(n-1):
            sum_road += ((town_coor[road[i1]][0] - town_coor[road[i1 +1]][0])**2 + (town_coor[road[i1]][1] - town_coor[road[i1 +1]][1])**2)**0.5
        sum_roads += sum_road
    print(sum_roads / factorial(n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
P = [(0, 0)]
for i in range(N):
    x, y = [int(_) for _ in input().split()]
    P.append((x, y))

s = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        d = math.sqrt((P[i][0] - P[j][0])**2 + (P[i][1] - P[j][1])**2)
        s += d

print(s/N)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

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



route = itertools.permutations([i for i in range(N)], N)
cnt = 0

for r in route:
    for i in range(N-1):
        xi = xy[r[i]][0]
        xj = xy[r[i+1]][0]
        yi = xy[r[i]][1]
        yj = xy[r[i+1]][1]
        cnt += math.sqrt((xi-xj)**2 + (yi-yj)**2)

print(cnt/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math


def main():
    n = int(input())
    town = [i for i in range(1, n + 1)]
    comb = list(itertools.permutations(town))
    pos = []
    for i in range(n):
        pos.append(list(map(int, input().split())))
    calc = []
    for c in comb:
        tmp = 0
        for i in range(0, len(c) - 1):
            tmp += distance(pos[c[i] - 1], pos[c[i + 1] - 1])
        calc.append(tmp)
    mea = sum(calc) / len(calc)
    print(mea)


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


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

from itertools import permutations
ways = list(permutations(range(n)))

from math import sqrt

def d(x1, y1, x2, y2):
    return sqrt((x1-x2)**2 + (y1 - y2)**2)

c=0

for way in ways:
    for i in range(len(way) - 1):
        c += d(x[way[i]], y[way[i]], x[way[i+1]], y[way[i+1]])

ans = c / len(ways)
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

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 += sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)

print(result/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

res = 0
cnt = 0
for pattern in itertools.permutations(cities, len(cities)):
    cnt += 1
    for i in range(n-1):
        res += math.sqrt((dots[pattern[i]][0] - dots[pattern[i+1]][0]) ** 2 + (dots[pattern[i]][1] - dots[pattern[i+1]][1]) ** 2)


print(res/cnt)

Submission status: Accepted

Solution code:
n = int(input())
place = []
for _ in range(n):
    place.append(list(map(int, input().split())))
    
import itertools
route = list(itertools.permutations(range(n), n))

import math

ans = 0
for i in range(len(route)):
    dist = 0
    for j in range(n-1):
        dist += math.sqrt((place[route[i][j+1]][0] - place[route[i][j]][0])**2 + (place[route[i][j+1]][1] - place[route[i][j]][1])**2)
    
    ans += dist

print(ans/len(route))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
dist = 0
town = [i for i in range(n)]
root_lis = itertools.permutations(town)# 全ての場合のリストを生成
for one_case in root_lis:
    x_prev, y_prev = x_y[one_case[0]][0], x_y[one_case[0]][1]
    for num in one_case:
        dist += math.sqrt((x_y[num][0] - x_prev)**2 + (x_y[num][1] - y_prev)**2)
        x_prev, y_prev = x_y[num][0], x_y[num][1]
print(dist / math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

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

distances = []
for root in itertools.permutations(range(1, n+1)):
    total = 0
    for i, j in enumerate(root):
        nxt_idx = (i+1) % len(root)
        nxt_root = root[nxt_idx]
        if nxt_idx == 0:
            break

        x1, y1 = roots[j-1]
        x2, y2 = roots[nxt_root-1]

        tmp = (x1 - x2)**2 + (y1-y2)**2
        distance = math.sqrt(tmp)
        total += distance

    distances.append(total)

ave = sum(distances) / len(distances)
print(ave)

Submission status: Accepted

Solution code:
import math
N = int(input())
p = []
d = []

def dfs(route, visited, n):
  total = 0
  if(len(route) == n + 1):
    for i in range(1, N):
      x1, y1 = d[route[i]]
      x2, y2 = d[route[i+1]]
      total += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
      
    return total

  route.append(0)

  for i in range(n):
    if(visited[i]):
      continue

    route[-1] = i
    v = visited[::]
    v[i] = True
    total += dfs(route[::], v, n)
  
  return total

for i in range(N):
  d.append(list(map(int, input().split())))

a = 1

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

print(dfs([-1], [False] * N, N) / a)

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
import numpy as np
import sys


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


N = ir()

roots = []
for i in range(N):
    x, y = lr()
    roots.append([x, y])

ans = 0
path_dict = {}
all_path = list(itertools.permutations(range(0, N, 1)))
for pattern in all_path:
    sum_dist = 0
    for n1, n2 in zip(pattern, pattern[1:]):
        path = sorted([n1, n2])
        # if key not in path_dict:
        p1 = roots[path[0]]
        p2 = roots[path[1]]
        dist = np.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
        # path_dict[key] = dist
        # else:
        #     dist = path_dict[path]

        sum_dist += dist
    ans += sum_dist
ans /= len(all_path)
print(ans)

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

ans=0
for perm in itertools.permutations(range(n)):
    l=0
    for j in range(n-1):
        l+=((x[perm[j+1]]-x[perm[j]])**2+(y[perm[j+1]]-y[perm[j]])**2)**0.5
    ans+=l
print(ans/math.factorial(n))

Submission status: Accepted

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

N = int(input())
XY = [[int(i) for i in input().split()] for _ in range(N)]
sum = 0.0
for p in permutations(range(N), N):
    for i in range(N - 1):
        now = p[i]
        next = p[i + 1]
        dx = abs(XY[next][0] - XY[now][0])
        dy = abs(XY[next][1] - XY[now][1])
        sum += sqrt(dx * dx + dy * dy)
print(sum / factorial(N))

Submission status: Accepted

Solution code:
import math
import itertools

class Pos():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
def distance(a,b):
    return math.sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))

points = []

num = int(input())
for i in range(num):
    x,y = input().split()
    points.append(Pos(int(x), int(y)))
    
total = 0
pattern = len(list(itertools.permutations(points)))

for l in itertools.permutations(points):
    n = len(l)
    for i in range(n-1):
        total = total + distance(l[i], l[i+1])
        
avg = total / pattern
print(avg)

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
plots = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    plots[i] = (x, y)

roots = list(permutations(range(n)))
tmp = 0
for root in roots:
    for i in range(n-1):
        tmp += ((plots[root[i]][0] - plots[root[i + 1]][0]) ** 2 + (plots[root[i]][1] - plots[root[i + 1]][1]) ** 2) ** 0.5

print(tmp / len(roots))

Submission status: Accepted

Solution code:
import math
from itertools import combinations
 
N = int( input() )
 
def distance( a, b ):
  x1, y1 = a
  x2, y2 = b
  return math.sqrt( ( x1 - x2 ) ** 2 + ( y1 - y2 ) ** 2 )
 
d = []
for i in range(N):
  x, y = map( int, input().split() )
  d.append( [x, y] )
 
base = list(combinations(range(N),2))
sums = 0
for x in base:
  a, b = x
  sums += distance( d[a], d[b] )
print( sums / (len(base)) * ( N - 1 ))

Submission status: Accepted

Solution code:

from itertools import permutations

n=int(input())
xy=[[0]*2 for i in range(n)]
a=[0]*n
for i in range(n):
    xy[i]=list(map(int,input().split()))
    a[i]=i    

icnt=0
rsum=0
for i in permutations(a):
    icnt+=1
    r=0
    for ii in range(len(i)-1):
        j=i[ii]
        k=i[ii+1]
        r=r+((xy[k][0]-xy[j][0])**2+(xy[k][1]-xy[j][1])**2)**0.5
    rsum=rsum+r

print(rsum/icnt)

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for _ in range(n):
	x,y=map(int, input().split())
	xy.append([x,y])

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

Submission status: Accepted

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


def main():
    N = int(input())
    locations = list()
    for _ in range(N):
        x, y = list(map(int, input().split(' ')))
        locations.append((x, y))
    # Calculate distance between two towns
    d = [[0 for _ in range(N)] for _ in range(N)]
    for edge in combinations(range(N), 2):
        from_town = edge[0]
        to_town = edge[1]
        from_x, from_y = locations[from_town]
        to_x, to_y = locations[to_town]
        d[from_town][to_town] = sqrt((from_x - to_x)**2 + (from_y - to_y)**2)
        d[to_town][from_town] = d[from_town][to_town]
    # Calculate total distance of each route
    route_d_sum = 0
    for route in permutations(range(N), N):
        route_d = 0
        for i in range(N - 1):
            route_d += d[route[i]][route[i + 1]]
        route_d_sum += route_d
    # Calculate average
    print(route_d_sum / factorial(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
dp = [[0.0 for _ in range(n)] for _ in range(n)]
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        if dp[a[i]][a[i + 1]] == 0.0:
            dp[a[i]][a[i + 1]] = sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
            dp[a[i + 1]][a[i]] = dp[a[i]][a[i + 1]]
        d += dp[a[i]][a[i + 1]]
print("{:10f}".format(d / c))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
dp = [[0.0 for _ in range(n)] for _ in range(n)]
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        if dp[a[i]][a[i + 1]] == 0.0:
            dp[a[i]][a[i + 1]] = sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
        d += dp[a[i]][a[i + 1]]
print("{:10f}".format(d / c))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

p = [i for i in range(n)]
c = 0
d = 0.0
for a in permutations(p):
    c += 1
    for i in range(n - 1):
        d += sqrt((x[a[i]] - x[a[i + 1]]) ** 2 + (y[a[i]] - y[a[i + 1]]) ** 2)
print("{:10f}".format(d / c))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools
from math import sqrt
N = int(input())
POINTS = []
for n in range(N):
    x,y = list(map(int,input().split()))
    POINTS.append({"x":x,"y":y})

ans = 0
num=0
for candidate in itertools.permutations(POINTS):
    num +=1
    for i,v in enumerate(candidate):
        if i == 0:
            continue
        prev = candidate[i-1]
        ans += sqrt((v["x"] - prev["x"]) ** 2 +(v["y"]-prev["y"]) ** 2)
print(str(ans/num))

Submission status: Accepted

Solution code:
import math
N=int(input())
zahyo=[]
alld=0
jac=math.factorial(N-1)*2
for i in range(0,N):
    zahyo.append(list(map(int,input().split())))
for i in range(0,N-1):
    for j in range(i+1,N):
        alld+=(((zahyo[i][0]-zahyo[j][0])**2+(zahyo[i][1]-zahyo[j][1])**2)**(1/2))*jac
print(alld/math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

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

total = 0
for i, p1 in enumerate(P[:-1]):
    for p2 in P[i+1:]:
        total += ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

print(total * 2 / N)

Submission status: Accepted

Solution code:
N=int(input())

import math
from itertools import permutations

town=[i+1 for i in range(N)]

roots = list(permutations(town))

# print(*roots,sep="\n")

info = []

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

total = 0 

for road in roots:
    for j in range(len(road)):
        if j==0:
            continue
        to = road[j]
        fr = road[j-1]

        total += math.sqrt( (info[to-1][0]-info[fr-1][0])**2 + (info[to-1][1] - info[fr-1][1])**2 )

print(total/math.factorial(N))