Problem:


Score : 300 points

Problem Statement

There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.

There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

\left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j)

(Added 21:12 JST) All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.

The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.

By calculating the lengths of the other paths in this way, we see that the average length of all routes is:

\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

There are two paths to visit the towns: 1 → 2 and 2 → 1. These paths have the same length.

Sample Input 3

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())

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

n = [i for i in range(N)]
sum = 0
for i in permutations(n):
    i = list(i)
    for j in range(N-1):
        sum += ((xy[i[j]][0]-xy[i[j+1]][0])**2 + (xy[i[j]][1]-xy[i[j+1]][1])**2)**(0.5)

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

print(sum/fct)

Submission status: Accepted

Solution code:
#
# abc145 c
#

import sys
from io import StringIO
import unittest
import math
import itertools


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
0 0
1 0
0 1"""
        output = """2.2761423749"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
-879 981
-866 890"""
        output = """91.9238815543"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310"""
        output = """7641.9817824387"""
        self.assertIO(input, output)


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

    L = [i for i in range(N)]
    R = itertools.permutations(L)

    all = 0
    for r in R:
        for pi in range(1, len(r)):
            all += math.sqrt((P[r[pi]][0]-P[r[pi-1]][0])**2 +
                             (P[r[pi]][1]-P[r[pi-1]][1])**2)

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

    print(f"{all/n:.10f}")


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
town = []
for n in range(N):
    x, y = map(int,input().split())
    town.append((x,y))

ans = 0
for i,j in combinations(town,2):
    ans += ((i[0]-j[0])**2 + (i[1]-j[1])**2)**0.5
print (2*ans/N)

Submission status: Accepted

Solution code:
#C - Average Length
import math
import itertools
N = int(input())
town = []
for i in range(N):
    x,y = map(int,input().split())
    town.append((x,y))

def dist(A,B):
    return math.sqrt((A[0]-B[0])**2 + (A[1]-B[1])**2)
route = list(itertools.permutations(town))
tot = 0
for i in route:
    for j in range(len(i)-1):
        tot += dist(i[j],i[j+1])
ave = tot/len(route)
print(ave)

Submission status: Accepted

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

dist = 0
cnt = 0
for target_list in list(itertools.permutations(n)):
    for i in range(len(target_list)):
        if i == 0:
            continue
        dist += math.sqrt((XY[target_list[i]][0] - XY[target_list[i-1]][0]) ** 2 + (XY[target_list[i]][1] - XY[target_list[i-1]][1]) ** 2)
    cnt += 1
print(dist / cnt)

Submission status: Accepted

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

import math
from itertools import permutations
list = [i for i in range(N)]
per = permutations(list,N)

ans = 0
for i in per:
    for j in range(N-1):
        x1, y1 = pos[i[j]]
        x2, y2 = pos[i[j+1]]
        ans += math.sqrt((x1-x2)**2 + (y1-y2)**2)
        
for n in range(1,N+1):
    ans /= n

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy

    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = [LI() for i in range(N)]
    dist = [[0 for i in range(N)] for i in range(N)]
    for index1, num1 in enumerate(mylist):
        for index2, num2 in enumerate(mylist):
            dist[index1][index2] = math.sqrt((num1[0]-num2[0])**2 + (num1[1]-num2[1])**2)
    result = 0
    index = 0
    seq = [i for i in range(N)]
    for i in itertools.permutations(seq):
        index += 1
        past = i[0]
        for num in i[1:]:
            result += dist[past][num]
            past = num
            
            
    print(result/index)

    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
	A[i],B[i]=map(int,input().split())
total=0
for i in range(N):
  for j in range(i+1,N):
    total+=((A[i]-A[j])**2+(B[i]-B[j])**2)**0.5
    
    

print(total/N*2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
N = int(readline())
XY = np.array(read().split(),np.int64)
 
X = XY[::2]; Y = XY[1::2]
 
dx = X[:,None] - X[None,:]
dy = Y[:,None] - Y[None,:]
 
dist_mat = (dx * dx + dy * dy) ** .5
 
answer = dist_mat.sum() / N
print(answer)

Submission status: Accepted

Solution code:
import collections # deque, Counter
import itertools # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect
import math # factorical（階乗)
# import heapq
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

cnt = math.factorial(n-1)
ans = 0

chkli = itertools.permutations(range(n),2)

for i, v in enumerate(chkli):
    ans += ((abs((li[v[0]][0]) - (li[v[1]][0])) ** 2) + (abs((li[v[0]][1]) - (li[v[1]][1])) ** 2)) **.5 * cnt

print(ans/(math.factorial(n)))

Submission status: Accepted

Solution code:
n=int(input())
l=[]

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

import itertools

seq=[i for i in range(n)]
p=list(itertools.permutations(seq))
import math

ans=0
for pp in p:
  for i in range(n-1):
    xy=math.sqrt((l[pp[i]][0]-l[pp[i+1]][0])**2 + (l[pp[i]][1]-l[pp[i+1]][1])**2)
    ans+=xy

print(ans/len(p))

Submission status: Accepted

Solution code:
import itertools
Row = int(input())
List = []
l=[]
for i in range (Row):
  l.append(i+1)
  List.append(list(map(int, input().split())))
x = 0
y = 0
mid = 0
p_list = list(itertools.permutations(l, Row))
for v in p_list:
  for i in range(1,Row):
    x = List[v[i]-1][0]-List[v[i-1]-1][0]
    y = List[v[i]-1][1]-List[v[i-1]-1][1]
    k = x*x+y*y
    mid += k**0.5
res = mid / len(p_list)
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations as perm

N = int(input())
XYS = [list(map(int, input().split())) for _ in range(N)]
s = 0
for indexes in perm(list(range(N))):
    xys = [XYS[i] for i in indexes]
    x0, y0 = xys[0]
    for x1, y1 in xys:
        s += ((x0 - x1)**2 + (y0 - y1)**2) ** 0.5
        x0 = x1
        y0 = y1

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XYS = [list(map(int, input().split())) for _ in range(N)]
s = 0
def perm(ns):
    acc = []
    def fill(ms, remains):
        if remains:
            for m in remains:
                fill(ms + [m], [x for x in remains if x != m])
        else:
            acc.append(ms)
    fill([], ns)
    return acc

s = 0
for indexes in perm(list(range(N))):
    xys = [XYS[i] for i in indexes]
    x0, y0 = xys[0]
    for x1, y1 in xys:
        s += ((x0 - x1)**2 + (y0 - y1)**2) ** 0.5
        x0 = x1
        y0 = y1

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

print(ans)

Submission status: Accepted

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

def rec(prefix, remains):
    if remains:
        for xy in remains:
            for xys in rec(prefix + [xy], [x for x in remains if x != xy]):
                yield xys
    else:
        yield prefix

s = 0
for xys in rec([], XYS):
    prev = xys.pop(0)
    for xy in xys:
        v = math.sqrt(((xy[0] - prev[0])**2) + ((xy[1] - prev[1])**2))
        prev = xy
        s += v

ans = s / math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(len(A)-1):
    for k in range(i+1,len(A)):
        ans.append((((A[i][0]-A[k][0])**2)+(A[i][1]-A[k][1])**2)**0.5)
print(sum(ans)*2/N)

Submission status: Accepted

Solution code:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
ans = []
import numpy as np
for i in range(len(A)-1):
    for k in range(i+1,len(A)):
        ans.append(np.sqrt(((A[i][0]-A[k][0])**2)+(A[i][1]-A[k][1])**2))
print(sum(ans)*2/N)

Submission status: Accepted

Solution code:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
ans = []
import numpy as np
import itertools
for zyun in itertools.permutations(range(N)):
    cnt = 0
    for k in range(len(zyun)-1):
        cnt += np.sqrt((A[zyun[k+1]][0]-A[zyun[k]][0])**2+(A[zyun[k+1]][1]-A[zyun[k]][1])**2 )
    ans.append(cnt)
print(sum(ans) / len(ans))

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
X = []
Y = []
num = []
for i in range(N):
  x,y = map(int,input().split())
  X.append(x)
  Y.append(y)
  num.append(i)
p = itertools.permutations(num, N)
count_sum = 0
for i in p:
  count=0
  for j,k in enumerate(i):
    if j<N-1:
      count+=math.sqrt((X[k]-X[i[j+1]])**2+(Y[k]-Y[i[j+1]])**2)
  count_sum+=count
      
print(count_sum/math.factorial(N))

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import permutations
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
ans=0
cnt=0
for i in permutations(range(N)):
  d=0
  for j in range(N-1):
    dx=xy[i[j+1]][0]-xy[i[j]][0]
    dy=xy[i[j+1]][1]-xy[i[j]][1]
    d+=sqrt(dx**2+dy**2)
  ans+=d
  cnt+=1
print(ans/cnt)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
l=[int(i) for i in range(n)]
ans=chk=p=0
w=[]
for i in range(n):
    x,y=map(int,input().split())
    w.append((x,y))
for i in list(itertools.permutations(l,n)):
    chk=0
    for j in range(n-1):
        chk+=((w[i[j]][0]-w[i[j+1]][0])**2+(w[i[j]][1]-w[i[j+1]][1])**2)**0.5
    ans+=chk
    p+=1

print(ans/p)

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import defaultdict
import math

def mapt(fn, *args):
    return tuple(map(fn, *args))

n = int(input())
cities = [mapt(int, input().split(" ")) for i in range(n)]
list1 = list(permutations(range(1, n+1), n))


def some(index1, index2):
    index1 -= 1
    index2 -= 1
    x1, y1 = cities[index1]
    x2, y2 = cities[index2]
    r = math.sqrt((x1-x2)**2 +(y1-y2)**2)
    # print(r)
    return r

ans = 0
for row in list1:
    for i in range(n-1):
        # print(row[i:i+2])
        ans += some(*row[i:i+2])
    # print()
print(ans/len(list1))

Submission status: Accepted

Solution code:
import math
from itertools import permutations 
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans_ = 0
count = 0
sum_list = list(permutations(range(N), N))
for nums in sum_list:
    for i in range(len(nums)-1):
        x1, y1 = xy[nums[i]]
        x2, y2 = xy[nums[i+1]]
        ans_ += math.sqrt((x1-x2)**2+(y1-y2)**2)
    count += 1
print(ans_ / count)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, factorial
n = int(input())
lst = [None]

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

ans = 0

for per in permutations(list(range(1,n+1))):
    lenth = 0
    for i in range(0,n-1):
        x1,y1 = lst[per[i]]
        x2,y2 = lst[per[i+1]]
        lenth += sqrt((x2-x1)**2 + (y2-y1)**2)
    ans += lenth

ans /= factorial(n)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import statistics


def main():
    N = int(input())
    city_lst = [list(map(int, input().split())) for _ in range(N)]
    d_lst = [0] * math.factorial(N)

    for i, route in enumerate(itertools.permutations(range(N))):
        for j in range(len(route) - 1):
            d = math.sqrt((city_lst[route[j + 1]][0] - city_lst[route[j]][0])
                          ** 2 + (city_lst[route[j + 1]][1] - city_lst[route[j]][1]) ** 2)
            d_lst[i] += d

    print(f"{statistics.mean(d_lst):.10f}")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n = int(input())
A = []
for _ in range(n):
    x,y = map(int,input().split())
    A.append([x,y])
tmp = 0
cnt = 0
for L in permutations(A):
    cnt += 1
    for i in range(1,len(L)):
            tmp += math.sqrt((L[i][0]-L[i-1][0])**2+(L[i][1]-L[i-1][1])**2)
print(tmp/cnt)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import math
from collections import defaultdict,deque
from itertools import permutations
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

t=ii()
lol=[]
for i in range(t):
    a,b=ml()
    lol.append([a,b])
yo=0    
cnt=0
for i in list(permutations(lol)):
    for j in range(1,len(i)):
        x=i[j][0]-i[j-1][0]
        y=i[j][1]-i[j-1][1]
        yo+=math.sqrt(x*x+y*y)
    cnt+=1
print(yo/cnt)

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

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = int(input())

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

p = [i for i in range(N)]
pp = list(itertools.permutations(p))

ans = 0
for ppp in pp:
    for i in range(1,N):
        ans += math.sqrt((x[ppp[i-1]][0]-x[ppp[i]][0])**2 + (x[ppp[i-1]][1]-x[ppp[i]][1])**2)

print(ans / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt,factorial
N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int, input().split())))
# print(L)

sum=0
for S in permutations(range(N)):
    tmp=0
    for i in range(N-1):
        tmp+= sqrt((L[S[i]][0]-L[S[i+1]][0])**2 + (L[S[i]][1]-L[S[i+1]][1])**2)
    sum+=tmp
print(sum/factorial(N))

Submission status: Accepted

Solution code:
#順列全探索の問題
#街の訪れ方はN!通りある
n=int(input())
from itertools import permutations
per=[i for i in range(n)]
per=list(permutations(per,n))

#まず累乗の関数
fac=[[0] for i in range(10)]
fac[0]=1
fac[1]=1
for i in range(2,10):
  fac[i]=i*fac[i-1]

#距離の関数
import math
def diff(a,b):
  return math.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)

#順列全探索
xy=[]
for i in range(n):
  x,y=list(map(int,input().split()))
  xy.append([x,y])

ans=0
for i in per:
  for j in range(1,n):
    ans=ans+diff(xy[i[j]],xy[i[j-1]])


print(ans/fac[n])

Submission status: Accepted

Solution code:
n=int(input())
city=[list(map(int,input().split())) for _ in range(n)]
length=[]
for i in range(n-1):
    for j in range(i+1,n):
        len=((city[i][0]-city[j][0])**2+(city[i][1]-city[j][1])**2)
        length.append(len**(0.5))
ans=sum(length)*2/n
print("{:.7f}".format(ans))

Submission status: Accepted

Solution code:
def rec(num, string, total, xy_list, n):
    x, y = xy_list[num]
    if string:
        pre_one = int(string[-1])
        pre_x, pre_y = xy_list[pre_one]
        distance = ((x - pre_x)**2 + (y - pre_y)**2)**0.5
        total+=distance
    string+=str(num)

    if len(string)==n:
        return total

    all_total = 0
    ret_list = [i for i in range(n) if str(i) not in string]
    for one in ret_list:
        all_total+=rec(one, string, total, xy_list, n)
    return all_total

def main():
    n = int(input())
    xy_list = []
    k = 1
    for i in range(n):
        x, y = list(map(int, input().split(" ")))
        xy_list.append((x, y))
        k*=(i+1)

    all_total = 0
    for i in range(n):
        all_total+=rec(i, "", 0, xy_list, n)
    print(all_total/k)

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):
    X,Y = map(int,input().split())
    x[i] = X 
    y[i] = Y
    
total = 0
cnt = 0
def dfs(now,rest):
    global total,cnt
    for next in rest:
        #cnt += 1 * factorial(len(rest)-1)
        total += math.sqrt((x[now]-x[next])**2 + (y[now]-y[next])**2) * factorial(len(rest)-1)
        rest2 = rest.copy()
        rest2.remove(next)
        dfs(next,rest2)
    return 

def factorial(N):
    if N == 1 or N == 0:
        return 1
    else:
        return N * factorial(N-1)
        
for i in range(N):
    A = [j for j in range(N)]
    A.remove(i)
    dfs(i,A)
    
#print(total)
#print(cnt) #has to be 282240 when N=8
#print(factorial(N))
print(total / factorial(N))

Submission status: Accepted

Solution code:
N = int(input())
pos = []
for _ in range(N):
    x,y = [int(v) for v in input().split()]
    pos.append((x,y))

path = []
def dfs(state):
    if len(state) == N:
        path.append(state)
        return
    for i in range(N):
        if i not in state:
            nstate = state[:]
            nstate.append(i)
            dfs(nstate)

dfs([])
ans = 0
for p in path:
    n = p[0]
    tmp = 0
    for nn in p[1:]:
        tmp += (abs(pos[n][0] - pos[nn][0]) ** 2 + abs(pos[n][1] - pos[nn][1]) ** 2) ** (1/2)
    ans += (tmp / len(path))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
m = math.factorial(n)
l = [list(map(int,input().split())) for i in range(n)]
x,y = [list(i) for i in zip(*l)]
z = list(range(n))
z = list(itertools.permutations(z))
ans = 0
for i in range(m):
    for j in range(n - 1):
        ans += math.sqrt((x[z[i][j]] - x[z[i][j+1]]) ** 2 + (y[z[i][j]] - y[z[i][j+1]]) ** 2)
print(ans / m)

Submission status: Accepted

Solution code:
import math
import itertools
from statistics import mean
n = int(input())
p = [list(map(int,input().split())) for i in range(n)]
ans = []
for v in itertools.permutations(p):
  length = 0
  for i in range(n-1):
    length += math.sqrt((v[i+1][0] - v[i][0])**2 + (v[i+1][1] - v[i][1])**2)
  ans.append(length)

print(mean(ans))

Submission status: Accepted

Solution code:
import math

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

a = []
for i in range(n-1):
    for j in range(i, n):
        a.append(((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**(1/2))
print(2*math.factorial(n-1)*sum(a)/math.factorial(n))

Submission status: Accepted

Solution code:
import numpy as np

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

X = XY[::2] ; Y = XY[1::2]

dx = X[:,None] - X[None, :]
dy = Y[:, None] - Y[None,:]

dist_mat = (dx*dx + dy*dy) ** .5

answer = dist_mat.sum() / N
print(answer)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

def distance(x2,x1,y2,y1):
    return ((x2-x1)**2 + (y2-y1)**2)**0.5

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

routes = list(itertools.permutations(range(N), N))
ans = []

for route in routes:
    dist = 0
    for i in range(1, N):
        dist += distance(X[route[i]], X[route[i-1]], Y[route[i]], Y[route[i-1]])
    ans.append(dist)

print(np.mean(ans))

Submission status: Accepted

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

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

dis = []
for i in range(n - 1):
    for j in range(i + 1, n):
        dis.append(((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])** 2) ** (1 / 2))

print(2 * math.factorial(n - 1) * sum(dis) / math.factorial(n))

Submission status: Accepted

Solution code:
import math

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

dis = []
for i in range(n-1):
    for j in range(i+1, n):
        dis.append(((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**(1/2))
print(2*math.factorial(n-1)*sum(dis)/(math.factorial(n)))

Submission status: Accepted

Solution code:
import itertools

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

memo = []
for i in range(n):
    memo.append(i)

ans = 0
count = 0
for v in itertools.permutations(memo, n):
    count += 1
    tmp_root = 0
    for i in range(1, n):
        tmp_root += ((ab[v[i-1]][0]-ab[v[i]][0])**2+(ab[v[i-1]][1]-ab[v[i]][1])**2)**0.5
    ans += tmp_root

print(ans/count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from itertools import permutations
    from math import sqrt

    n = int(input())
    x = [0 for _ in range(n)]
    y = [0 for _ in range(n)]

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

    path = list(permutations(range(n)))
    path_count = len(path)
    length = 0

    for p in path:
        for i, j in zip(p, p[1:]):
            length += sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)

    print(length / path_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = []

for _ in range(N):
    L.append(list(map(int,input().split())))

ans = 0

for i in range(N-1):
    for j in range(i + 1, N):
        ans += ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5

ans *= 2 / N

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import math
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5

N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        A[i][j] = dist(X[i],X[j])
tot = 0
for x in permutations(range(N),N):
    cnt = 0
    for i in range(1,N):
        cnt += A[x[i-1]][x[i]]
    tot += cnt
print(tot/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
from math import sqrt
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ans = 0
cnt = 0
for v in itertools.permutations(list(range(n))):
    for i in range(n-1):
        x = (xy[v[i]][0]-xy[v[i+1]][0]) ** 2
        y = (xy[v[i]][1]-xy[v[i+1]][1]) ** 2
        ans += sqrt(x+y)
    cnt += 1
print(ans/cnt)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
div = fact(n)
for lst in itertools.permutations(range(n), n):
    start = xy[lst[0]]
    for pos in lst:
        dx = start[0] - xy[pos][0]
        dy = start[1] - xy[pos][1]
        d = (dx ** 2 + dy ** 2) ** 0.5
        ans += d / div
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

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

ll = list(range(0,n))
perml = list(permutations(ll, n))

val = 0
for perm in perml:
    prev_x = 0
    prev_y = 0
    for i,p in enumerate(perm):
        x,y = xyl[p]
        if i == 0:
            prev_x = x
            prev_y = y
        else:
            val += sqrt( (prev_x-x)**2 + (prev_y-y)**2 )
            prev_x = x
            prev_y = y
    
ans = val/len(perml)
print(ans)

Submission status: Accepted

Solution code:
import math

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

s = 0
for i in range(n):
    xi, yi = p[i]
    for j in range(i+1, n):
        xj, yj = p[j]
        s += math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
s = s * 2 / n
print(s)

Submission status: Accepted

Solution code:
import math

def cal(n):
    if n == 1:
        return 0
    else:
        return (n-1)+cal(n-1)
n = int(input())
x = [None]*n
y = [None]*n
total = 0
for i in range(n):
    x[i], y[i] = map(int, input().split())

for i in range(n):
    for j in range(n):
        total += math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)
total = total/2
ans = total*(n-1)/cal(n)

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
l = list(range(n))

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

ans = 0 
def clc_distandce(a,b):
    [x1, y1] = a
    [x2, y2] = b
    dist = math.sqrt((a[0] - b[0])**2 + (a[1]-b[1])**2)
    return dist


for i in itertools.permutations(l,n):
    #print(i)
    #print(list(i)[0])
    for k in range(1,n):
        dist = clc_distandce(pos_list[list(i)[k]],pos_list[list(i)[k-1]])
        ans += dist
    #print(ans)
    #print()
    
print(ans/math.factorial(n))

Submission status: Accepted

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

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

def calc(a,b):
    [x1, y1] = a
    [x2, y2] = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))

sum = 0
for i in permutations(range(n)):
    distance = 0
    for j in range(1, n):
        distance = calc(xy[i[j]], xy[i[j-1]])
        sum += distance
print(sum/factorial(n))

Submission status: Accepted

Solution code:
n=int(input())
x,y=[],[]
for i in range(n):
    x1,y1=map(int,input().split())
    x.append(x1)
    y.append(y1)
s=0
for i in range(n):
    for j in range(n):
        if i!=j:
            s+=((x[i]-x[j])**2+(y[i]-y[j])**2)**(1/2)
print(s/n)

Submission status: Accepted

Solution code:
import itertools as it

n = int(input())
lst = []
for i in range(n):
	x, y = list(map(int, input().split()))
	lst.append([x, y])
perm = list(it.permutations(lst))

cost = []
for i in perm:
	temp = 0
	for j in range(len(i)-1):
		temp += (((i[j][0] - i[j+1][0])**2) + ((i[j][1] - i[j+1][1])**2))**0.5
	cost.append(temp)

print(sum(cost) / len(cost))

Submission status: Accepted

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

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

def calc(a, b):
    [x1, y1] = a
    [x2, y2] = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 -y2, 2))
ans = 0
for order in permutations(range(N)):
    tmp = 0
    for i in range(1, N):
        tmp += calc(l[order[i]], l[order[i-1]])
    ans += tmp
print(ans/factorial(N))

Submission status: Accepted

Solution code:
import math
N = int(input())
x = []
y = []
for i in range(N):
  tmp = input().split(" ")
  x.append(int(tmp[0]))
  y.append(int(tmp[1]))

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

print(d/N)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

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

s = 0 #合計
for p in path:
    before = [lst[p[0]][0], lst[p[0]][1]]
    for i in range(1, N):
        s += sqrt((lst[p[i]][0] - before[0])**2 + (lst[p[i]][1] - before[1])**2)
        before[0] = lst[p[i]][0]
        before[1] = lst[p[i]][1]

#n!の計算
n = 1
for i in range(1, N+1):
    n *= i

print(s/n)