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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
n = INT()
xy = [LIST() for _ in range(n)]
a = list(permutations(xy, n))
l = len(a)
ans = 0
for i in range(l):
    tmp = 0
    for j in range(n - 1):
        tmp += sqrt((a[i][j][0] - a[i][j+1][0]) ** 2 + (a[i][j][1] - a[i][j+1][1]) ** 2)
    ans += tmp
ans /= l
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from math import sqrt
a=[]
for _ in range(int(input())):
    a.append([int(i) for i in input().split()])
summ=0
for i in a:
    for j in a:
        summ+=sqrt((i[0]-j[0])**2+(i[1]-j[1])**2)
print(summ/len(a))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement as cwr , combinations , permutations ,product
from math import sqrt
a=[]
for _ in range(int(input())):
    a.append([int(i) for i in input().split()])
p=list(permutations(a))
ans=[]
for i in p:
    cur=0
    for j in range(len(i)-1):
        cur+=sqrt((i[j+1][0]-i[j][0])**2+(i[j+1][1]-i[j][1])**2)
    ans.append(cur)
print(sum(ans)/len(ans))

Submission status: Accepted

Solution code:
import itertools
import math
N=int(input())
town=[list(map(int,input().split())) for _ in range(N) ]
sum=0
cnt=0
for path in itertools.permutations(town,N):
    cnt+=1
    for i in range(N-1):
        sum+=math.sqrt((path[i][0]-path[i+1][0])**2+(path[i][1]-path[i+1][1])**2)
print(sum/cnt)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
xy  = [[int(i) for i in input().split()] for j in range(N)]
distance = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        xi = xy[i][0]
        yi = xy[i][1]
        xj = xy[j][0]
        yj = xy[j][1]
        d = math.sqrt((xi-xj)**2+(yi-yj)**2)
        distance[i][j] = d
        distance[j][i] = d

print(sum([sum(i) for i in distance])/N)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
xy  = [[int(i) for i in input().split()] for j in range(N)]
distance = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        xi = xy[i][0]
        yi = xy[i][1]
        xj = xy[j][0]
        yj = xy[j][1]
        d = math.sqrt((xi-xj)**2+(yi-yj)**2)
        distance[i][j] = d
        distance[j][i] = d

anslist=[]
for route in itertools.permutations(range(N),N):
    total=0
    for i in range(N-1):
        start = route[i]
        goal = route[j]
        total += distance[start][goal]
    anslist.append(total)

print(sum(anslist)/len(anslist))

Submission status: Accepted

Solution code:
#145_C
from itertools import permutations
from math import factorial
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]

res=0
for l in permutations(range(n)):
    res+=sum([((xy[l[i+1]][0]-xy[l[i]][0])**2+(xy[l[i+1]][1]-xy[l[i]][1])**2)**0.5 for i in range(n-1)])
print(res/factorial(n))

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
  xy.append(list(map(int,input().split())))
ans = 0
for i in range(N):
  for j in range(N):
    if i != j:
      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:
import math
n = int(input())
coo = [list(map(int,input().split())) for i in range(n)]
sum = 0
for i in range(n):
    for j in range(i,n):
        sum += math.sqrt((coo[i][0]-coo[j][0])**2 + (coo[i][1]-coo[j][1])**2)

ans = 2 * sum / float(n)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

def solve(l):
    r = 0
    for i in range(len(l)-1):
        x_i = l[i][0]
        y_i = l[i][1]
        x_i_1 = l[i+1][0]
        y_i_1 = l[i+1][1]

        r += math.sqrt(pow(x_i_1 - x_i,2) + pow(y_i_1 - y_i,2))

    return r

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

    p = list(itertools.permutations(xy, len(xy)))
    result = 0

    for i in range(len(p)):
        result += solve(list(p[i]))

    print(result/len(p))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math


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

pairs = list(itertools.permutations(A, N))

ans = 0
for p in pairs:
    x1, y1 = p[0]
    for i in range(1, N):
        x2, y2 = p[i]
        ans += math.hypot(x1-x2, y1-y2)
        x1, y1 = x2, y2

ans /= len(pairs)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math


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


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
pairs = list(itertools.product(A, A))
pairs = [calc_diff(p[0], p[1]) for p in pairs]
ans = sum(pairs) / 2 * 2 / N
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
from itertools import permutations
perm = list(permutations(s,n))
def distance(s):
    res = 0
    for i in range(n-1):
        res += ((s[i][0]-s[i+1][0])**2 + (s[i][1]-s[i+1][1])**2)**0.5
    return res
k = 0
for key in perm:
    k += distance(key)
fin_res = format(k/len(perm),'.10f')
print(fin_res)

Submission status: Accepted

Solution code:
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
from itertools import permutations
def distance(s):
    res = 0
    for i in range(n-1):
        res += ((s[i][0]-s[i+1][0])**2 + (s[i][1]-s[i+1][1])**2)**0.5
    return res
k = 0
for key in list(permutations(s,n)):
    k += distance(key)
fin_res = format(k/len(list(permutations(s,n))),'.10f')
print(fin_res)

Submission status: Accepted

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

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF = float("inf")
import itertools

N = INT()
xy = [tuple(MAP()) for _ in range(N)]

dist_list=[]
for i in itertools.permutations(xy, N):
    dist = 0
    for j in range(1, N):
        dist += ((i[j-1][0]-i[j][0])**2 + (i[j-1][1]-i[j][1])**2)**0.5
    dist_list.append(dist)

print(sum(dist_list)/len(dist_list))

Submission status: Accepted

Solution code:
from itertools import permutations

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

Length = []
permutation = list(permutations(range(0, N)))

for i in range(len(permutation)):
    L = 0
    for j in range(len(permutation[i]) - 1):
        L += (
            (place[permutation[i][j]][0] - place[permutation[i][j + 1]][0]) ** 2
            + (place[permutation[i][j]][1] - place[permutation[i][j + 1]][1]) ** 2
        ) ** (1 / 2)
    Length.append(L)

print(sum(Length) / len(permutation))

Submission status: Accepted

Solution code:
import math
import itertools
def distance(x1,x2,y1,y2):
    return math.sqrt(((x2-x1)**2) + ((y2-y1)**2))
n = int(input())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
t = [i for i in range(n)]
for i in range(len(x)):
    x[i],y[i] = map(int,input().split())
pattern = [_ for _ in itertools.permutations(t,n)]
dis_all = [0 for _ in range(len(pattern))]
for i in range(len(pattern)):
    for j in range(n-1):
        dis_all[i] += distance(x[pattern[i][j]],x[pattern[i][j+1]],y[pattern[i][j]],y[pattern[i][j+1]])
print(sum(dis_all)/len(dis_all))

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
permu_list = itertools.permutations(range(N))
ans=0
c = 0
for p in permu_list:
  c += 1
  for i in range(N-1):
    ans += ((A[p[i]][0]-A[p[i+1]][0])**2+(A[p[i]][1]-A[p[i+1]][1])**2)**0.5
print(ans/c)

Submission status: Accepted

Solution code:
n=int(input())
XY=[]
for i in range(n):
  XY.append(tuple(map(int,input().split())))
def d(x1,y1,x2,y2):
  return ((x2-x1)**2+(y2-y1)**2)**0.5
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=d(XY[i][0],XY[i][1],XY[j][0],XY[j][1])*2/n
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 0
for i, (x, y) in enumerate(XY):
    for u, v in XY[i + 1:]:
        ans += dist(x, y, u, v)

print(2 * ans / N)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

N = int(input())
points = [tuple([int(x) for x in input().split()]) for _ in range(N)]

routes = permutations(range(N), r=N)

sum_dist = 0
for r in routes:
    for i in range(N - 1):
        (x_0, y_0), (x_1, y_1) = points[r[i]], points[r[i + 1]]
        sum_dist += ((x_0 - x_1)**2 + (y_0 - y_1)**2)**0.5

print(sum_dist / factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, factorial
import sys
input = sys.stdin.readline


def dist(xy1, xy2):
    x1, y1 = xy1
    x2, y2 = xy2
    return sqrt((x1-x2)**2 + (y1-y2)**2)


def main():
    n = int(input())
    lst = [tuple(map(int, input().split())) for _ in range(n)]
    sum_d = 0
    for perm in permutations(range(n)):
        d = 0
        for i in range(n-1):
            d += dist(lst[perm[i]], lst[perm[i+1]])
        sum_d += d
    print(sum_d / factorial(n))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

avg = 0.0
count = 0
for perm in permutations(range(N)):
    count += 1
    # print(perm)
    cost =  0
    for i in range(N - 1):
        pi, pj = perm[i], perm[i + 1]
        dij = ((xy[pi][0] - xy[pj][0]) ** 2 + (xy[pi][1] - xy[pj][1]) ** 2) ** 0.5
        cost += dij
    avg += cost
print(avg / count)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import heapq
import collections
import itertools
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())


inputDataList = []
data = []
for i in range(n):
    inputData = input().split()
    inputDataList = [int(n) for n in inputData]
    data.append(inputDataList)

mat = [[-1 for i in range(n)] for j in range(n)] #二次元の静的確保


def calc_dis(x1, y1, x2, y2):
    dis = pow(x1 - x2, 2) + pow(y1 - y2, 2)
    dis = math.sqrt(dis)
    return dis


def path_dis(path):
    dis = 0
    for i in range(len(path)-1):
        dis += mat[path[i]][path[i+1]]
    return dis

for i in range(n):
    for j in range(n):
        mat[i][j] = calc_dis(data[i][0], data[i][1], data[j][0], data[j][1])

perm = list(itertools.permutations(range(n)))

ans = 0
for p in perm:
    tmp_ans = path_dis(p)
    ans += tmp_ans

ans = ans/len(perm)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Plist = []
c = 0
for i in range(N):
    c += i
    Plist.append(list(map(int,input().split())))
import math
    
D = 0
for j in range(N):
    for k in range(N):
        if j <= k :
            continue
        D += math.sqrt((Plist[j][0]-Plist[k][0])**2 + (Plist[j][1]-Plist[k][1])**2)
print(D*(N-1)/c)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
import itertools
N=int(input())
d=defaultdict(float)
l=[]
for i in range(N):
  x,y=map(int,input().split())
  l.append([x,y])
for i in range(N-1):
  for j in range(i+1,N):
    x1,y1=l[i][0],l[i][1]
    x2,y2=l[j][0],l[j][1]
    d[(i,j)]=(math.sqrt((x1-x2)**2+(y1-y2)**2))
    d[(j,i)]=(math.sqrt((x1-x2)**2+(y1-y2)**2))

tot=0
for pat in itertools.permutations([i for i in range(N)]):
  for i in range(N-1):
    tot+=(d[(pat[i],pat[i+1])])
print(tot/math.factorial(N))

Submission status: Accepted

Solution code:
import math
N=int(input())
d=[]
l=[]
for i in range(N):
  x,y=map(int,input().split())
  l.append([x,y])
for i in range(N-1):
  for j in range(i+1,N):
    x1,y1=l[i][0],l[i][1]
    x2,y2=l[j][0],l[j][1]
    d.append(math.sqrt((x1-x2)**2+(y1-y2)**2))
print(2*sum(d)/N)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for q in permutations(data):
    for i in range(1,n):
        ans += dist(q[i-1],q[i])
for i in range(n):
    ans /= (i+1)
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(n):
        ans += dist(data[i],data[j])

print(ans/n)

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations
def dist(a,b):
    return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for q in permutations(data):
    for i in range(1,n):
        ans += dist(q[i-1],q[i])
for i in range(n):
    ans /= (i+1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
l = []
x = []
y = []
for i in range(n):
    l.append(i+1)
    tmp_x, tmp_y = map(int, input().split())
    x.append(tmp_x)
    y.append(tmp_y)

permutation = list(itertools.permutations(l, n))

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

print(ans / len(permutation))

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
print(sum(((x-z)**2+(y-w)**2)**.5 for x,y in l for z,w in l)/n)

Submission status: Accepted

Solution code:
n = int(input())
ll = [list(map(int,input().split())) for _ in range(n)]
import itertools as it
c,d = 0,0
for t in it.permutations(range(n)):
  c += 1
  for i in range(len(t)-1):
    d += ((ll[t[i+1]][1]-ll[t[i]][1])**2+(ll[t[i+1]][0]-ll[t[i]][0])**2)**.5
print(d/c)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)


def main():
    N = I()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = MI()

    ans = 0
    for cities in permutations(range(N)):
        for i in range(1, len(cities)):
            ans += distance(x[cities[i-1]], y[cities[i-1]], x[cities[i]], y[cities[i]])

    print(ans / math.factorial(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
town = list(itertools.permutations(range(N)))
dis = []
for i in range(N):
    s = tuple(map(int,input().split()))
    dis.append(s)
    
ans = 0
for i in town:
    for j in range(len(i)-1):
        calc =  math.sqrt((dis[i[j]][0]-dis[i[j+1]][0])**2 + (dis[i[j]][1]-dis[i[j+1]][1])**2) 
        ans += calc
    
print(ans/len(town))

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


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


route = 0
for i in range(N):
    for j in range(i + 1, N):
        route+=dist(x[i], y[i], x[j], y[j])
ave = (route * (2 * math.factorial(N - 1))) / math.factorial(N)
print(ave)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
x, y = [0]*n, [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i], y[i] = a, b
l = list(itertools.permutations(range(n)))

tmp = 0
for p in l:
    for j in range(n-1):
        a = p[j]
        b = p[j+1]
        tmp += math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)

print(round(tmp/len(l), 10))

Submission status: Accepted

Solution code:
import itertools
import sys
import math
input = sys.stdin.readline

N = int(input())
x = []
y = []

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

ans = 0
j = 0
num_old = 0

lis = [x for x in range(N)] # 0からn-1までのリスト
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力
for one_case in permutations_lis:
    i = 0
    j += 1
    for num in one_case:
#        print(num, end=" ")
        if i != 0:
            ans += math.sqrt((x[int(num_old)]-x[int(num)])**2+(y[int(num_old)]-y[int(num)])**2)
#            print(ans)
        i += 1
        num_old = num
#    print("")

#print (j)
ans = ans / j
print (ans)

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline

N = int(input())
x = []
y = []

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

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
#        print ("i="+str(i)+", j="+str(j))
#        print ("xi="+str(x[i])+", xj="+str(x[j]))
#        print ("yi="+str(y[i])+", yj="+str(y[j]))
        ans += math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)

ans = ans / N
print (ans)

Submission status: Accepted

Solution code:
import numpy as np 
import itertools
N = int(input())
pos = []
for _ in range(N):
    pos.append(list(map(int,input().split())))
pos = np.array(pos)

dist_dict = {}
def dist(n0,n1): # inputはノード番号
    k = str(min(n0,n1))+str(max(n0,n1))
    if k in dist_dict:
        d = dist_dict[k]
    else:
        d = np.sqrt(np.sum(np.power(pos[n1]-pos[n0],2)))
        dist_dict[k] =d
    return d

pattern_list = list(itertools.permutations(range(N))) # 順列の生成
ans = 0
for pattern in pattern_list:
    pre_node = pattern[0]
    for i in range(1,N):
        next_node = pattern[i]
        ans+=dist(pre_node,next_node)
        pre_node = next_node

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
from math import factorial
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        pow(
            pow(route[i][0] - route[i + 1][0], 2) +
            pow(route[i][1] - route[i + 1][1], 2), .5) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
from math import factorial
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        np.sqrt(
            pow(route[i][0] - route[i + 1][0], 2) +
            pow(route[i][1] - route[i + 1][1], 2)) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))

Submission status: Accepted

Solution code:
n = int(input())
town = [list(map(int,input().split())) for _ in range(n)]
ans = 0
def dist(a,b,c,d):
	return ((a-c)**2+(b-d)**2)**0.5
for i in range(n):
	for j in range(n):
		ans += dist(town[i][0],town[i][1],town[j][0],town[j][1])
print(ans/(n))

Submission status: Accepted

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


indexes_permutaions = list(itertools.permutations(indexes))
costs = []
for indexes_permutaion in indexes_permutaions:
    cost = 0
    for i in range(len(indexes_permutaion) - 1):
        index = indexes_permutaion[i]
        next_index = indexes_permutaion[i + 1]
        num = math.sqrt((((cities[next_index][0] - cities[index][0])
                          ** 2) + ((cities[next_index][1] - cities[index][1]) ** 2)))
        cost += num
    costs.append(cost)
print(float(sum(costs)) / len(costs))

Submission status: Accepted

Solution code:
import itertools
import math


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


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

s = 0
for cmb in itertools.combinations(C, 2):
    s += 2 * dist(cmb[0], cmb[1]) / N

print(s)

Submission status: Accepted

Solution code:
import itertools
import math


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


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

s = 0
for per in itertools.permutations(C):
    for i in range(N-1):
        s += dist(per[i], per[i+1])

print(s / len(list(itertools.permutations(C))))

Submission status: Accepted

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

for j in range(N-1):
    for k in range(j+1,N):
        S+=math.sqrt((X[j]-X[k])**2+(Y[j]-Y[k])**2)
        
print(round(S*2/N,10))

Submission status: Accepted

Solution code:
N=int(input())
point=[list(map(int,input().split())) for i in range(N)]
distance=0
for i in range(N-1):
    for j in range(i+1,N):
        try:
            a,b=tuple(point[i])
            c,d=tuple(point[j])
            a-=c
            b-=d
            distance+=(a**2+b**2)**(1/2)
        except:
            continue
print(2*distance/N)

Submission status: Accepted

Solution code:
import math
import itertools

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

# 二次元配列を用意してa→bの全てのパターンの経路を計算する
min_load_map = []
for i in range(N):
  arr = []
  for t in range(N):
    min_i_to_t = math.sqrt((a[i][0] - a[t][0])**2 + (a[i][1] - a[t][1])**2)
    arr.append(min_i_to_t)
  min_load_map.append(arr)

ans = float()

# 順列を用意
patterns = itertools.permutations(range(N))
count = 0
for pat in patterns:
  count += 1
  pat = list(pat)
  tmp = 0
  for p in range(1, len(pat)):
    tmp += min_load_map[pat[p-1]][pat[p]]
  ans += tmp

ans /=  count
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    a, b = (int(x) for x in input().split())
    xy.append([a, b])
    
def distance(d, xy, i, j):
    return (
              (xy[i][0] - xy[j][0]) ** 2
            + (xy[i][1] - xy[j][1]) ** 2
        ) ** 0.5
 
import itertools
d = []
l1 = [x for x in range(N)]
for v in itertools.permutations(l1, N):
    l2 = list(v)
    d0 = []
    for c in range(N-1):
        i = l2[c]
        j = l2[c+1]
        d0.append(distance(d, xy, i, j))
    d.append(sum(d0))
 
print(sum(d) / len(d))

Submission status: Accepted

Solution code:
import itertools
n=int(input())

x,y=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)
l=list(itertools.permutations(range(n)))
 
wrk=0
for p in l:
    for j in range(0,n-1):
        a=p[j]
        b=p[j+1]
        wrk+=((x[a]-x[b])**2+(y[a]-y[b])**2)**0.5
print(wrk/len(l))

Submission status: Accepted

Solution code:
n = int(input())

dist = [[0] * n for _ in range(n)]
town = []
for i in range(n):
   x, y = map(int, input().split())
   town.append([x, y])

for i in range(n):
   for j in range(i+1, n):
      d = ((town[i][0]-town[j][0])**2+(town[i][1]-town[j][1])**2)**0.5
      dist[i][j] = d
      dist[j][i] = d

dist2 = [sum(x) for x in dist]
print(sum(dist2)/n)

Submission status: Accepted

Solution code:
import itertools
n=int(input())

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

l=list(itertools.permutations(range(n)))

a=0
for p in l:
    for j in range(0,n-1):
        a+=((x[p[j]]-x[p[j+1]])**2+(y[p[j]]-y[p[j+1]])**2)**0.5
print(a/len(l))

Submission status: Accepted

Solution code:
from itertools import permutations
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
a=0
for p in permutations([i for i in range(n)]):
  for j in range(1,n):
    a+=((x[p[j]]-x[p[j-1]])**2+(y[p[j]]-y[p[j-1]])**2)**0.5
for i in range(1,n+1):
  a/=i
print(a)

Submission status: Accepted

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

perm_towns = list(itertools.permutations(towns))
sum_length = 0
for i in range(len(perm_towns)):
    for j in range(n-1):
        length = ((perm_towns[i][j][0]-perm_towns[i][j+1][0]) **2 + (perm_towns[i][j][1] - perm_towns[i][j+1][1]) **2) **0.5
        sum_length += length 

ans = sum_length / (len(perm_towns))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

city = []
for _ in range(N):
    x, y = map(int,input().split(" "))
    city.append((x,y))
    
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        x1, y1 = city[i]
        x2, y2 = city[j]
        
        ans += ( ( (x2-x1)**2 + (y2-y1)**2 )**0.5 )*(2/N)
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
towns = []
for _ in range(n):
    x,y = map(int,input().split())
    towns.append((x,y))
dist = []
for i in range(n-1):
    for j in range(i+1,n):
        x1,y1 = towns[i]
        x2,y2 = towns[j]
        dist.append(np.sqrt((x1-x2)**2+(y1-y2)**2))
print((sum(dist)/len(dist)) * (n-1))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
towns = []
for _ in range(n):
    x,y = map(int,input().split())
    towns.append((x,y))
dist = []
for i in range(n-1):
    for j in range(i+1,n):
        x1,y1 = towns[i]
        x2,y2 = towns[j]
        dist.append(np.sqrt((x1-x2)**2+(y1-y2)**2))
print((sum(dist)/len(dist)) * (n-1))

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
import math

n = int(stdin.readline().rstrip())
l = [int(x) for x in range(n)]
p = itertools.permutations(l, n)

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

total = 0
for i in p:
    for j in range(n - 1):
        p1 = i[j] - 1
        p2 = i[j + 1] - 1
        dis = math.sqrt((xy[p2][0] - xy[p1][0])**2 +
                        (xy[p2][1] - xy[p1][1])**2)
        total += dis

print(total/math.factorial(n))

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  xy=[list(map(int,input().split())) for _ in [0]*n]
  ans=0
  for i in range(n):
    xi,yi=xy[i][0],xy[i][1]
    for j in range(i+1,n):
      xj,yj=xy[j][0],xy[j][1]
      ans+=pow(pow(xi-xj,2)+pow(yi-yj,2),0.5)
  print(ans*2/n)
  # (各ペア間距離の総和)*2*(n-1)!/n!=(各ペア間距離の総和)*2/n
if __name__ == '__main__':
    main()