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 numpy
import math

def main():
  n = int( input() )
  
  x = []
  y = []
  
  for i in range(n):
    x_tmp, y_tmp = (int(x) for x in input().split())
    
    x.append( x_tmp )
    y.append( y_tmp )
  
  cnt = 0.0
  
  for i in range(n):
    for j in range(i,n):
      distance = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])
      cnt = cnt + (math.sqrt( distance ) * (n-1))
  
  waru = 0
  
  for i in range(n):
    waru = waru + i
  
  #cnt = cnt / math.factorial(n)
  cnt = cnt / waru
  
  print( cnt )

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
import math
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n + 1):
    try:
        x[i], y[i] = map(int, input().split())
    except EOFError:
        break
zen = []
for j in range(n):
    for k in range(n):
        d = math.hypot((x[j] - x[k]), (y[j] - y[k])) * math.factorial(n - 1)
        zen.append(d)
a = sum(zen) / math.factorial(n)
print(a)

Submission status: Accepted

Solution code:
from itertools import *
n=int(input());a=[list(map(int,input().split()))for _ in range(n)];print(sum(((b-c)**2+(d-e)**2)**0.5for (b,d),(c,e) in product(a,repeat=2))/n)

Submission status: Accepted

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

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

#output
import math

sum = 0
for i in range(N):
    for j in range(N):
        sum += math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)
M = math.factorial(N)

print(sum/N)

Submission status: Accepted

Solution code:
import math
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]
dissum=0.0
def get_distance(x1, y1, x2, y2):
    d = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return d
for i in range(0,n):
    for j in range(0,n):
        d = get_distance(e[i][0], e[i][1], e[j][0], e[j][1])
        dissum+=d
bai=(n-1)/math.factorial(n)
print(dissum/n)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
 
def calculate_total_distance(order, distance_matrix):
    idx_from = np.array(order[:-1])
    idx_to = np.array(order[1:])
    distance_arr = distance_matrix[idx_from, idx_to]

    return np.sum(distance_arr)
  
n = int(input())
li = np.array([list(map(int, input().split())) for _ in range(n)])
x = li[:, 0]
y = li[:, 1]
dist_matrix = np.sqrt((x[:, np.newaxis] - x[np.newaxis, :]) ** 2 + (y[:, np.newaxis] - y[np.newaxis, :]) ** 2)
dist = 0
for num, i in enumerate(itertools.permutations(range(n))):
  dist += calculate_total_distance(list(i), dist_matrix)
    
print(dist / (num + 1))

Submission status: Accepted

Solution code:
from itertools import *
n=int(input());a=[list(map(int,input().split()))for _ in range(n)];print(sum(((b-c)**2+(d-e)**2)**0.5 for (b,d),(c,e) in product(a,repeat=2))/n)

Submission status: Accepted

Solution code:
import itertools, math

def calcDistance(town_a, town_b):
    distance = math.sqrt((town_a[0] - town_b[0]) ** 2 + (town_a[1] - town_b[1]) ** 2)
    return distance

N = int(input())

towns =[]
for i in range(N):
    town = [int(s) for s in input().split()]
    towns.append(town)
    
loute_patterns = [v for v in itertools.permutations(towns)]

pattern_distances = []

for i in range(len(loute_patterns)):
    pattern_distance = 0
    for j in range(len(loute_patterns[i])-1):
        distance = calcDistance(loute_patterns[i][j], loute_patterns[i][j+1])
        pattern_distance += distance
    pattern_distances.append(pattern_distance)
    
output = sum(pattern_distances) / len(pattern_distances)
print(output)

Submission status: Accepted

Solution code:
import math

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

c = 2
for i in range(2,n+1):
  c = math.factorial(i-2)*2 + c * (i-2)

dis = 0
for i in range(n):
  for j in range(i+1,n):
    dis = dis + pow((pow((lis[i][0] - lis[j][0]),2) + pow((lis[i][1] - lis[j][1]),2)),0.5)

ans = dis * c / math.factorial(n)

print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import permutations

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

acc = 0
for route in permutations(towns, n):
    dist = 0
    for i in range(n-1):
        x1, y1 = route[i]
        x2, y2 = route[i+1]
        dist += math.sqrt((x1-x2)**2 + (y1-y2)**2)
    acc += dist
print(acc / math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import *
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
print(sum(((b-c)**2+(d-e)**2)**0.5 for (b,d),(c,e) in product(a,repeat=2))/n)

Submission status: Accepted

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

dist_list = []
start_num = int(0)

while start_num!=n-1:
  for index in range(start_num+1,n):
    dist_list.append( ((coord[start_num][0]-coord[index][0])**2+(coord[start_num][1]-coord[index][1])**2)**0.5 )
  start_num+=1

print(sum(dist_list)*(n-1)/len(dist_list))

Submission status: Accepted

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


def d(i, j):
    return pow((ps[i][0] - ps[j][0])**2 + (ps[i][1] - ps[j][1])**2, 0.5)

p = itertools.permutations(range(n), n)

c = 0
ss = 0
for k in p:
    c += 1
    for i in range(n-1):
        ss += d(k[i], k[i+1])
print(ss/c)

Submission status: Accepted

Solution code:
import sys
import math

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

n=int(input())
xy=[input().strip().split() for i in range(n)]

k = 0

for Mfrom in range (n):
	for Mto in range (n):
		k = k + kyori(xy[Mfrom],xy[Mto])
        
print(k/n)
  
sys.exit()

Submission status: Accepted

Solution code:
import math
import itertools
import statistics

N = int(input())

x = []
y = []

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

dist_list = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(i+1,N):
        distance = math.sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2)
        dist_list[i][j] = distance


l = [i for i in range(N)]
#print(l)
dist_sum = 0
dist_sum_list = []

for v in itertools.permutations(l, N):
    for i in range(N-1):
        if v[i] < v[i+1]:
            dist_sum += dist_list[v[i]][v[i+1]]
        else:
            dist_sum += dist_list[v[i+1]][v[i]]
    dist_sum_list.append(dist_sum)
    dist_sum = 0
    
mean = statistics.mean(dist_sum_list)
print(mean)

Submission status: Accepted

Solution code:
import math


def ncr(l, m):
    return math.factorial(l) // math.factorial(l - m) // math.factorial(m)


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

for i in range(n):
    for j in range(n):
        if i > j:
            info.append(math.sqrt((map_l[i][0] - map_l[j][0])**2 + (map_l[i][1] - map_l[j][1])**2))
p = (math.factorial(n) * (n-1) / ncr(n, 2))
print(sum(info) * p / math.factorial(n))

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

s = 0
for j in range(N):
    for k in range(N):
        if (j!=k):
            s += ((x[j] - x[k])**2 + (y[j] - y[k])**2)**(1/2)
if N==2:
    a = s / math.factorial(N)
else:
    a = s*(N-1)*math.factorial(N-2)/math.factorial(N)
print(a)

Submission status: Accepted

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

n=int(input())
l=[]
num=1
for _ in range(n):
    num*=_+1
a=2
for k in range(3,n):
    a*=(k-1)
for i in range(n):
    x,y=map(int,input().split())
    l.append([x,y])
ans=[]
i=0
for i in range(n-1):
    for j in range(i+1,n):
        c=((l[j][0]-l[i][0])**2+(l[j][1]-l[i][1])**2)**(0.5)
        ans.append(c)
s=sum(ans)*(n-1)*a/num
print(s)

Submission status: Accepted

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

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

fa = math.factorial(n)
it = [i for i in range(n)]
itt =  list(itertools.permutations(it))

ans = 0

for idxlist in itt:
    for i in range(n-1):
        j = i+1
        # print(i, j)
        # print([idxlist[i]], [idxlist[j]])
        # print(xy[idxlist[i]][0], xy[idxlist[j]][0])

        ans += np.sqrt((xy[idxlist[i]][0]-xy[idxlist[j]][0])**2+(xy[idxlist[i]][1]-xy[idxlist[j]][1])**2)
        # print(ans)
    # print(' ')

print(ans/fa)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
x,y = [],[]
for i in range(n):
    x_y_str = input()
    x.append(int(x_y_str.split(" ")[0]))
    y.append(int(x_y_str.split(" ")[1]))
tmp_dist = 0
for i in itertools.permutations(range(n)):  # 0, 1, 2
    tmp = None
    for node in list(i):
        if tmp == None:
            tmp = node
        else:
            tmp_dist += math.sqrt(pow(x[tmp]-x[node],2)+pow(y[tmp]-y[node],2))
            tmp = node
print(tmp_dist/math.factorial(n))

Submission status: Accepted

Solution code:
import math
 
N = int(input())
place_list = [input().split() for i in range(N)] 
 
distances = []
 
for i, one_place in enumerate(place_list[:len(place_list)]):
    mini_distances = []
    for another_cordinate in place_list[i+1:]:
        distance = math.sqrt((int(one_place[0]) - int(another_cordinate[0])) ** 2 + (int(one_place[1]) - int(another_cordinate[1])) ** 2)
        distances.append(distance)
 
distances = [n*math.factorial(N-1) for n in distances]
 
print(2*sum(distances)/math.factorial(N))

Submission status: Accepted

Solution code:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def main():
    n = int(input())
    xy = []
    for i in range(n):
        x,y = map(int,input().split())
        xy.append([x,y])
    dist = 0
    a = [i for i in range(n)]
    lst = list(itertools.permutations(a))
    for l in lst:
        res = 0
        now = 10
        for i in l:
            if now>=n:
                now = i
            else:
                dist += math.sqrt((xy[now][0]-xy[i][0])**2+(xy[now][1]-xy[i][1])**2)
                now = i
    ans = dist/len(lst)
    print(ans)
    return


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import math
def calc(x_i,x_j,y_i,y_j):
    tmp = ((x_i)-(x_j))**2
    tmp += ((y_i)-(y_j))**2
    return math.sqrt(tmp)
N = int(input())
array = []
for _ in range(N):
    array.append(list(map(int, input().split())))
sum = 0
check = []
kai = 1
for i in range(1,N+1):
    kai *= i
    if i == N - 1:
        tmp = kai
for i in range(N):
    for k in range(N):
        if k == i:
            continue
        sum += calc(array[i][0],array[k][0],array[i][1],array[k][1])
sum *= tmp
print(sum/kai)

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
import math
n=int(input())
x=[]
y=[]
for i in range(n):
    xn,yn=map(int,input().split())
    x.append(xn)
    y.append(yn)
sum=0
for i in range(n):
    for j in range(n):
        if i!=j:
            sum+=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
mul=1
for i in reversed(range(1,n)):#(n-1)!
    mul*=i
sum*=mul
for i in range(n):
    sum/=i+1
print(sum)

Submission status: Accepted

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

ans=0

for i in range(N-1):
    for j in range(i+1,N):

        a=numpy.array(S[i])
        b=numpy.array(S[j])
        u=b-a
        ans+=numpy.linalg.norm(u)*math.factorial(N-1)*2

print(ans/math.factorial(N))

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())
t = 0
for i in range(n-1):
  for j in range(i+1, n):
    t += (((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5)/(n/2)
print(t)

Submission status: Accepted

Solution code:
import math

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

length = 0

for i in range(N):
    for j in range(N):
        lenlen = math.sqrt((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)
        length += lenlen

print(length/N)

Submission status: Accepted

Solution code:
import itertools
import math
import functools

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

def f(a, b):
    return l(a[0], a[1], b[0], b[1])

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

s = []
for p in itertools.permutations(xy):
    r = 0
    for i in range(len(p)-1):
        r += (f(p[i], p[i+1]))
    s.append(r)
print(sum(s) / len(s))

Submission status: Accepted

Solution code:
N = int(input())
d = [list(map(int,input().split())) for i in range(N)]
#print(d[1][0])
s=0
for x in range(0,N):
  for y in range(0,N):
    s += (((d[x][0]-d[y][0])**2)+((d[x][1]-d[y][1])**2))**(1/2)

print(s/N)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

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

N_fac = math.factorial(N)
towns = [x for x in range(N)]

perm = itertools.permutations(towns)

dist = 0
for i, v in enumerate(perm):
    for j in range(len(v)-1):
        tmp_dist = math.sqrt( (x[v[j]] - x[v[j+1]])**2 + (y[v[j]] - y[v[j+1]])**2 )
        dist += tmp_dist

print(dist/N_fac)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

xys = []
for _ in range(N):
	x,y = map(float,input().split())
	xys.append((x,y))
	
#print(xys)

#print(math.factorial(N))

ps = [i for i in range(N)]

ds = 0
for arr in itertools.permutations(ps):
	#print(arr)
	for j in range(N-1):
		p1 = arr[j]
		p2 = arr[j+1]
		#print(p1,p2)
		d = ((xys[p2][0]-xys[p1][0])**2+(xys[p2][1]-xys[p1][1])**2)**(1/2)
		ds += d
		#print("*",d,ds)
		
print(ds/math.factorial(N))

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations, permutations

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


def mean_dis(data):
    comb = permutations(data, n)
    sum = 0
    count = 0
    for c in comb:
        count += 1
        for i in range(1, len(c)):
            _c = np.array([c[i-1], c[i]])
            euclid = np.sqrt(np.sum((_c[0]-_c[1]) ** 2))
            sum += euclid
    return sum/count


def mean_dis2(data, n):
    comb = combinations(data, 2)
    all_dis = 0
    for c in comb:
        _c = np.array([c[0], c[1]])
        euclid = np.sqrt(np.sum((_c[0] - _c[1]) ** 2))
        all_dis += euclid

    return (all_dis*2)/n

print(mean_dis2(ls, n))

Submission status: Accepted

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

def kaijou(n):
    if n == 1:
        return 1
    else:
        return n * kaijou(n-1)
p = [2, 2*2, 2*2*3, 2*2*3*4,  2*2*3*4*5,  2*2*3*4*5*6, 2*2*3*4*5*6*7, 2*2*3*4*5*6*7*8]
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        #print(i+1 ,j+1)
        diff = (((xn[i] - xn[j]) ** 2) + ((yn[i] - yn[j]) ** 2)) ** 0.5
        #print(diff)
        ans += diff *  ( p[n-2])
nkaijou = kaijou(n)
print(ans/ nkaijou)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import numpy as np

def get_distance(x, y, i, j):
    a = np.array([x[i], y[i]])
    b = np.array([x[j], y[j]])
    return np.linalg.norm(b-a)

def solve(N: int, x: "List[int]", y: "List[int]"):
    dist_list = []
    num_path = N*(N-1)//2
    for i in range(N):
        for j in range(N):
            if i == j:
                dist = 0
            else:
                dist = get_distance(x, y, i, j)
            dist_list.append(dist)
    K = math.factorial(N-1)*2
    ans = sum(dist_list)/2*K/math.factorial(N)
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from itertools import combinations, permutations

def dist(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5


n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
edges = list(range(n))
memo = {}
res = 0
for p in permutations(edges):
    for i, a in enumerate(p[1:], start=1):
        b = p[i - 1]
        if (a, b) in memo:
            res += memo[a, b]
        else:
            d = dist(xy[a][0], xy[a][1], xy[b][0], xy[b][1])
            memo[a, b] = d
            memo[b, a] = d
            res += d
print(res / math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import combinations, permutations
import math
import numpy as np
import sys
readline = sys.stdin.readline
N = int(readline())
coords = []
for _ in range(N):
  xi, yi = map(int, readline().split())
  coords.append((xi,yi))
  
D = np.zeros((N, N))
for i, j in combinations(range(N), 2):
  xi, yi = coords[i]
  xj, yj = coords[j]
  
  dist = math.sqrt(
    (xi - xj)**2 + (yi - yj)**2
  )
  D[i, j] = dist
  D[j, i] = dist

sum = 0
l = 0
for c in permutations(range(N)):
  dist = 0
  for i in range(len(c)-1):
    dist += D[c[i], c[(i+1)]]
  sum += dist
  l += 1

# print(l)
print(sum/l)

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())
    
ans = 0
for i in range(n):
  for j in range(n):
    if i != j:
      ans += ((x[i] - x[j])**2 +  (y[i] - y[j])**2 )**0.5

print(ans / n)

Submission status: Accepted

Solution code:

#2
#-879 981
#-866 890
def f():
    N = int(input())
    a = []
    for i in range(N):
        aa = list(map(int, input().split(" ")))
        a.append(aa)
    
    s = [False]*N
    ta = []
    dm = {}
    ad = []
    dfs(a, s, ta, dm, ad)
    r = sum(ad)/len(ad)
    print(r)
    
def dfs(a, s, ta, dm, ad):
    if len(ta) == len(s):
        pr = ta[0]
        dd = 0
        for p in ta:
            pp = str(pr) + str(p)
            if pp in dm:
                dd += dm[pp]
            else:
                dp = ((p[0] - pr[0])**2 + (p[1] - pr[1])**2)**0.5 
                dm[pp] = dp
                dm[str(p) + str(pr)] = dp
                dd += dp
            pr = p
        ad.append(dd)
            
    for i in range(len(a)):
        if s[i] == False:
            s[i] = True
            ta.append(a[i])
            dfs(a,s, ta,dm, ad)
            ta.pop()
            s[i] = False

f()

Submission status: Accepted

Solution code:
import math
from itertools import permutations
N = int(input())
coodinate = [list(map(int,input().split())) for _ in range(N)]
f_N = math.factorial(N)
SumDistance = 0
j = 0
for val in permutations(coodinate):
    #if j >= math.factorial(N) // 2:
    #    break
    #print(val)
    for i in range(N-1):
        SumDistance += ((val[i+1][0] - val[i][0]) ** 2 + (val[i+1][1] - val[i][1]) ** 2) ** (1 / 2)
    #j += 1

print(SumDistance / math.factorial(N))

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 numpy as np

d=[0]*N*(N-1)
k=0
for i in range(N):
  for j in range(N):
    if i!=j:
      a=np.array([x[i], y[i]])
      b=np.array([x[j], y[j]])
      u=b-a
      d[k]=np.linalg.norm(u)
      k+=1

ans=sum(d)/N
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
nn = 2 * math.factorial(n-1)
cnt = 1
ave = 0
x = [0]*n
y = [0]*n
for i in range(n):
    x[i],y[i] = (int(l) for l in input().split())
for i in range(n):
    if i == n-1:
        print(ave / math.factorial(n))
    else:
        for j in range(n-cnt):
            k = i + j + 1
            ave += float(((x[i]-x[k]) ** 2 + (y[i]-y[k]) ** 2)) ** 0.5 * nn
        cnt += 1

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools

def main():
	#N, D = [int(x) for x in input().split()]
	N = int(input())
	c = []
	for i in range(N):
		x, y = [int(x) for x in input().split()]
		c.append([x, y])
	
	c = np.array(c)
	
	patterns = list(itertools.permutations(range(N)))

	a = 0
	dic = {}
	for p in patterns:
		for row in range(N-1):
			if str(p[row])+str(p[row+1]) in dic:
				a += dic[str(p[row])+str(p[row+1])]
				continue
			d = np.linalg.norm(c[p[row]] - c[p[row+1]])
			dic[str(p[row])+str(p[row+1])] = d
			a += d
	print(a/len(patterns))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
import itertools

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

N = math.factorial(n)
Sum = 0
for ls in itertools.permutations(range(n)):
    x_tmp = x[ls[0]]
    y_tmp = y[ls[0]]
    for j in range(1,n):
        dist = (x_tmp - x[ls[j]])**2 + (y_tmp - y[ls[j]])**2
        x_tmp = x[ls[j]]
        y_tmp = y[ls[j]]
        Sum += math.sqrt(dist)
print(Sum/N)

Submission status: Accepted

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

def f(i, j):
    return ((X[i] - X[j])**2 + (Y[i] - Y[j])**2)**0.5



N = int(readline())
jj = [1]*(N+1)
for i in range(1, N+1):
    jj[i] = jj[i-1]*i

XY = [map(int, readline().split()) for _ in range(N)]
X, Y = map(list, zip(*XY))
sumi = 0

L = list(range(N))
for k in permutations(L):
    for i in range(N-1):
        sumi += f(k[i], k[i+1])

print(sumi/jj[N])

Submission status: Accepted

Solution code:
import math
a = int(input())
x = []
y = []
temp = 0

for i in range(a):
	e = list(map(int, input().split(" ")))
	x.append(e[0])
	y.append(e[1])

# print(x, y)
for i in range(len(x)):
	tempx = x[i]
	tempy = y[i]
	xm = x
	ym = y
	del xm[i]
	del ym[i]
	# print(xm, ym)

	for j in range(len(xm)):
		temp += math.sqrt((xm[j] - tempx) ** 2 + (ym[j] - tempy) ** 2)

	x.insert(i, tempx)
	y.insert(i, tempy)
	# print(x, y)
print(temp/a)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

xy = []

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


#メモ化テーブル( N * 2)
#町 i と　j の距離
dis = [ [0 for col in range(N)] for row in range(N) ]

#二点間の距離を求めておく
for i in range(N):
    for j in range(N):
        dis[i][j] = math.sqrt( (xy[j][0] - xy[i][0]) ** 2 +(xy[j][1] - xy[i][1]) ** 2 )

perm = []
for i in range(N):
    perm.append(i)

ans = 0

for v in itertools.permutations(perm):
    for i in range(len(v)-1):
        ans += dis[v[i]][v[i+1]]

print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
import math
import itertools
import numpy as np

def main():
    n = int(input())
    xyls = []
    ans = 0

    for i in range(n):
        xyls.append(list(map(int, input().split())))

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

    nkai = math.factorial(n)
    ls = np.array([[0.0]*n]*n)

    for i in range(n):
        for j in range(n):
            tmp = 0
            tmp += (xyls[i][0] - xyls[j][0])*(xyls[i][0] - xyls[j][0])
            # print(tmp)
            tmp += (xyls[i][1] - xyls[j][1])*(xyls[i][1] - xyls[j][1])
            # print(tmp)
            tmp = tmp**0.5
            # print(tmp)
            ls[i][j] = tmp

    anssum = 0
    # print(ls)

    for i in pls:
        # print(i)
        for j in range(n-1):
            # print(ls[i[j]][i[j+1]])
            # print(i[j], i[j+1])
            # print(ls)
            # print(type(i[j]))
            anssum = anssum + ls[int(i[j])][int(i[j+1])]
            # print(anssum)

    ans = anssum / nkai
    # print(ls)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())
coordinate_list = [input().split() for i in range(N)] 

distance_list = []

for i, one_coordinate in enumerate(coordinate_list[:len(coordinate_list)]):
    mini_distance_list = []
    for another_cordinate in coordinate_list[i+1:]:
        distance = math.sqrt((int(one_coordinate[0]) - int(another_cordinate[0])) ** 2 + (int(one_coordinate[1]) - int(another_cordinate[1])) ** 2)
        distance_list.append(distance)
        #mini_distance_list.append(distance)
    #distance_list.append(mini_distance_list)

distance_list = [n*math.factorial(N-1) for n in distance_list]

print(2*sum(distance_list)/math.factorial(N))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
T = [np.array([int(i) for i in input().split()])for i in range(N)]
S = 0
for i in range(N-1):
    for j in range(i,N):
        S = S + np.linalg.norm(T[i]-T[j])
print(S*2/N)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
xy = []
sum_xy = 0

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

xy_itertools = list(itertools.permutations(xy, n))
fac = math.factorial(n)

for i in range(fac):
    for j in range(n):
        if j != n - 1:
            a = math.sqrt((((xy_itertools[i][j][0] - xy_itertools[i][j + 1][0])) ** 2) + (((xy_itertools[i][j][1] - xy_itertools[i][j + 1][1])) ** 2))
            sum_xy += a

print(sum_xy / fac)

Submission status: Accepted

Solution code:
import math
import itertools

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

cntnum = 0
tmp = []
for i, j in itertools.product(na, na):
    if i != j:
        cntnum += 1
        cntwa = 0
        # print(i, j)
        cntwa += ((a[i][0] - a[j][0]) ** 2 + (a[i][1] - a[j][1]) ** 2) ** 0.5
        # print(cntwa)
        tmp.append(cntwa)
print(sum(tmp)/n)

Submission status: Accepted

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



print(ans*2/n)

Submission status: Accepted

Solution code:
import numpy as np
import math
import itertools
N = int(input())
data = [list(map(int,input().split())) for _ in range(N)]
length_list = []
arr = np.arange(1,N+1)
list_arr = arr.tolist()
for v in itertools.permutations(list_arr,N):
    S = 0
    for i in range(N-1):
        S += np.sqrt((data[v[i]-1][0]-data[v[i+1]-1][0])**2+(data[v[i]-1][1]-data[v[i+1]-1][1])**2)
    length_list.append(S)
ave = sum(length_list)/math.factorial(N)
print(ave)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import itertools
n=int(input())  #数値入力 「N」だけの入力のとき
i=0
lst = []
while i < n: 
    a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
    lst.append([a,b])
    i+=1

conp=[]
for i,j in itertools.combinations(lst, 2):
    conp.append(math.sqrt((i[0]-j[0])*(i[0]-j[0])+(i[1]-j[1])*(i[1]-j[1])))

length_sum = sum(float(i) for i in conp)
print(math.factorial(n-1) * 2 * length_sum/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools
n = int(input())
x = [0]*n
y = [0]*n
for i in range(n):
    x[i],y[i] = [int(j) for j in input().split()]
# print(n,x,y)
dict = {}
for i in range(n):
    for j in range(n):
        if i < j:
            dict[str(i)+str(j)] = math.sqrt((x[i] - x[j])**2 + (y[i]- y[j])**2)

# print(dict)
# perm = [n for n in range(n)]
# print(perm)
sumation = 0
# print(len([v for v in itertools.permutations(perm,n)]))
# for p for perm:
#     for i in p: #それぞれのまち
#         if i == 0:
#             continue
#         else:
#             sum
# list = [v for v in dict.values()]
# # print(type(list))
# sumation = sum(list)
# # print(sumation)
# sumation = sumation * math.factorial(n)
# # print(sumation)
# for kei, length in dict.items():
#     if n != 2:
#         sumation -= length*2*math.factorial(n-2)
#     else:
#         continue
# # print(sumation)
# print(sumation/math.factorial(n))
for kei,length in dict.items():
    sumation += (n-1) * math.factorial(n-2)*length*2
print(sumation/math.factorial(n))