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

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

ans=0
for v in itertools.permutations(range(N)):
    for i in range(N-1):
        ans+=math.sqrt((XY[v[i]][0]-XY[v[i+1]][0])**2+(XY[v[i]][1]-XY[v[i+1]][1])**2)

print(ans/math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math

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

num = [i for i in range(N)]
distance_list = []
for perm in itertools.permutations(num):
    prev = None
    distance = 0
    for v in perm:
        if prev is None:
            prev = v
        else:
            distance += math.sqrt((X[prev] - X[v]) ** 2 + (Y[prev] - Y[v]) ** 2)
    distance_list.append(distance)

print(sum(distance_list) / len(distance_list))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]

INF=float("inf")

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

from itertools import permutations
import math

sum=0
for p in permutations(range(n)):
    for i in range(n-1):
        sum+=(pow((s[p[i]][0]-s[p[i+1]][0]),2)+pow((s[p[i]][1]-s[p[i+1]][1]),2))**0.5
print(sum/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools

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

ans = 0
for v in itertools.permutations(range(N)):
    for i in range(N-1):
        ans += math.sqrt((XY[v[i]][0]-XY[v[i+1]][0])**2 + (XY[v[i]][1]-XY[v[i+1]][1])**2)

print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
n = int(input())
dat = []
import itertools
for _ in range(n):
    x, y = map(int, input().split())
    dat.append((x,y))
import math
allsum = 0
for a in itertools.permutations(range(n)):
    x, y = dat[a[0]]
    s = 0
    for b  in range(1, n):
        nx, ny = dat[a[b]]
        s += math.sqrt( (nx-x)**2 + (ny-y)**2 )
        x, y = nx, ny
    allsum += s
res = allsum / math.factorial(n)
print(res)

Submission status: Accepted

Solution code:
import itertools


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

sum_dist = 0
num_pattern = 0

for pattern in itertools.permutations([i for i in range(n)], n):
    for i in range(1, n):
        x, y = geo[pattern[i]]
        x_prev, y_prev = geo[pattern[i-1]]
        d = ((x-x_prev) ** 2 + (y-y_prev) ** 2) ** 0.5
        sum_dist += d
    num_pattern += 1

print(sum_dist / num_pattern)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import math

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

num_list = []
city_name = []
ans = []
num = int(input())
queue = np.zeros((num,num))

for i in range(num):
  num_list.append(list(map(int,input().split())))
  city_name.append(i+1)


com = list(itertools.permutations(city_name, 2))
way = list(itertools.permutations(city_name, num))

for i in range(0,len(com)):
  a = num_list[com[i][0]-1]
  b = num_list[com[i][1]-1]
  queue[com[i][1]-1][com[i][0]-1] = distance(a,b)

for i in range(0,len(way)):
  sum = 0
  for j in range(0,num-1):
    sum = sum + queue[way[i][j]-1][way[i][j+1]-1]
  ans.append(sum)

print(np.mean(ans))

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
points = []
for _ in range(N):
    points.append(tuple(map(int, input().split(" "))))

distances = [[0 for _ in range(N)] for __ in range(N)]
for si in range(N):
    for ei in range(N):
        distances[si][ei] = ((points[si][0] - points[ei][0]) ** 2 +
                             (points[si][1] - points[ei][1]) ** 2) ** 0.5

total = 0
for route in itertools.permutations([i for i in range(N)]):
    for s, e in zip(route, route[1:]):
        total += distances[s][e]

print(total / math.factorial(N))

Submission status: Accepted

Solution code:
import sys
import math
from scipy.misc import comb  # atcoderではspecial→misc, permは使えない

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N - 1):
    for l in range(i + 1, N):
        ans += math.sqrt((xy[i][0] - xy[l][0]) ** 2 + (xy[i][1] - xy[l][1]) ** 2)
ans *= (N - 1) / comb(N, 2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
L = list(itertools.permutations(xy))
ans = 0
for i in L:
    dis = 0
    for l in range(N-1):
        dis += math.sqrt((i[l][0]-i[l+1][0])**2 + (i[l][1] - i[l+1][1])**2)
    ans += dis
print(ans / len(L))

Submission status: Accepted

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

a = 0
b = 0
for i in range(n):
  t = list(range(n))
  t.remove(i)
  for j in t:
    a += ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5
    b += 1
    
print(a*(n-1)/b)

Submission status: Accepted

Solution code:
from itertools import permutations as perm
from math import factorial

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

all_sum = 0
for a in perm(XY):
    sum_num = 0
    for j in range(N-1):
        x1, y1 = a[j]
        x2, y2 = a[j+1]
        r = (abs(x1-x2)**2 + abs(y1-y2)**2)**(1/2)
        sum_num += r
    all_sum += sum_num

print(all_sum / factorial(N))

Submission status: Accepted

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

t = 1
for i in range(1, N - 1):
  t *= i

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    x1, y1 = xy[i]
    x2, y2 = xy[j]
    ans += (((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2)) * (N - 1) * 2 * t

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

ans /= n

print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        D[i][j] = dist(A[i],A[j])
cnt = 0
for z in permutations(range(N),N):
    for i in range(N):
        cnt += D[z[i]][z[j]]
print(cnt/math.factorial(N))

Submission status: Accepted

Solution code:
import sys
import itertools
import math

N = int(sys.stdin.readline())

towns = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split(" "))
    towns.append((x, y))

dist = 0
count = 0
patterns = itertools.permutations(towns)
for pattern in patterns:
    count += 1
    pre_x, pre_y = 0, 0
    for i, (x, y) in enumerate(pattern):
        if i > 0:
            dist += math.sqrt((x - pre_x)**2 + (y - pre_y)**2)
        pre_x, pre_y = x, y

print(dist / count)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=0
for poss in itertools.permutations([i for i in range(n)]):
  for i in range(n-1):
    x1,y1=arr[poss[i]]
    x2,y2=arr[poss[i+1]]
    ans+=((x1-x2)**2+(y1-y2)**2)**0.5
for i in range(1,n+1):
  ans/=i
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

# 入力
n = int(input())
town = dict()
for i in range(n):
    x, y = map(int, input().split())
    town[i] = [x, y]


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


total = 0
for p in itertools.permutations(town, n):
    bef = p[0]
    for i in p[1:]:
        total += distance(town[bef], town[i])
        bef = i

print(total/math.factorial(n))

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

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

sum = 0
for i in range(N):
    for j in range(N):
        if i != j:
            sum = sum + sqrt( (x[i] - x[j])*(x[i] - x[j])+(y[i] - y[j])*(y[i] - y[j]) )

print (sum/N)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inpuS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

from itertools import permutations

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
P = list(permutations(XY))
ans = 0
count = 0
for p in P:
  for i in range(1,len(p)):
    dist = ((p[i-1][0]-p[i][0])**2 + (p[i-1][1]-p[i][1])**2)
    ans += dist**0.5
print(ans/len(P))

Submission status: Accepted

Solution code:
def ABC106_B():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    ans = 0
    for i in range((N+1)//2):
        cur = i*2+1
        if len(make_divisors(cur))==8:
            ans += 1
    print(ans)
    return

def ABC122_B():
    S = SI()
    ans = 0
    cur = 0
    d = {"A","C","G","T"}
    for s in S:
        if s in d:
            cur += 1
        else:
            ans = max(ans,cur)
            cur = 0
    ans = max(ans,cur)
    print(ans)
    return

def paken2019_C():
    N, M = LI()
    A = [LI()for _ in range(N)]
    T = [i for i in range(M)]
    ans = 0
    for t1,t2 in itertools.permutations(T,2):
        cur = 0
        for i in range(N):
            cur += max(A[i][t1],A[i][t2])
        ans = max(ans,cur)
    print(ans)
    return

def ABC95_C():
    A, B, C, X, Y = LI()
    if A+B<=C*2:
        ans = A*X+B*Y
    else:
        if X>Y:
            ans = Y*C*2 + min(A,C*2)*(X-Y)
        else:
            ans = X*C*2 + min(B,C*2)*(Y-X)
    print(ans)
    return

def SMTB_D():
    def flag(n,s):
        for l in range(n,N):
            if S[l]==str(s):
                return l
        return N
    N = I()
    S = SI()
    ans = 0
    for i in range(10):
        L1 = flag(0,i)
        for j in range(10):
            L2 = flag(L1+1,j)
            for k in range(10):
                L3 = flag(L2+1,k)
                if L3<N:
                    ans += 1
                    #print(i,j,k)
    print(ans)
    return

def JOI2007_3():
    N = I()
    V = [LI() for _ in range(N)]
    D = set()
    for vx,vy in V:
        D.add((vx,vy))
    ans = 0
    for i in range(N):
        a1, b1 = V[i]
        for j in range(i+1,N):
            a2, b2 = V[j]
            va, vb = a2 - a1, b2 - b1
            if (a1 + vb, b1 - va) in D and (a2 + vb, b2 - va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
            if (a1 - vb, b1 + va) in D and (a2 - vb, b2 + va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
    print(ans)
    return
"""
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
"""# 10

def square869120Contest():
    def length(a,b,x,y):
        if x>y:
            x,y = y,x
        rep = 0
        if a<x:
            rep += (x-a)*2
        if y<b:
            rep += (b-y)*2
        rep += (y-x)
        return rep
    N = I()
    AB = [LI()for _ in range(N)]
    ans = inf
    for i in range(N):
        s = AB[i][0]
        for j in range(N):
            g = AB[j][1]
            cur = 0
            for k in range(N):
                cur += length(AB[k][0],AB[k][1],s,g)
            ans = min(ans,cur)
    print(ans)
    return

def JOI7_D():
    M = I()
    S = [LI()for _ in range(M)]
    Ss = [(0,0)]
    curx,cury = S[0]
    for sx,sy in S[1:]:
        Ss.append((sx-curx,sy-cury))
        curx = sx; cury = sy
    #print(Ss)
    N = I()
    X = [LI()for _ in range(N)]
    D = set()
    for i in range(N):
        cur = (X[i][0],X[i][1])
        D.add(cur)
    for i in range(N):
        flag = True
        curx, cury = X[i]
        for k in range(M):
            curx += Ss[k][0]
            cury += Ss[k][1]
            #print(curx,cury)
            if not (curx, cury) in D:
                flag = False
                break
        if flag:
            #print(i,X[i])
            ansx = X[i][0] - S[0][0]
            ansy = X[i][1] - S[0][1]
            print(ansx,ansy)
            return
    return

def ABC128_C():
    N, M = LI()
    S = [[]for _ in range(N)]
    for i in range(M):
        s = LI()
        for j in s[1:]:
            S[j-1].append(i)
    P = LI()
    #print(S)
    loop = 2**N
    ans = 0
    for i in range(loop):
        p = [0]*M
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j)
        for k in cur:
            for l in S[k]:
                p[l] += 1
        flag = True
        for j in range(M):
            if p[j]%2!=P[j]:
                flag = False
        if flag:
            ans += 1
    print(ans)
    return

def ABC2_D():
    N, M = LI()
    V = set()
    for _ in range(M):
        x,y = LI()
        V.add((x,y))
    loop = 2**N
    ans = 0
    #print(V)
    for i in range(loop):
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j+1)
        flag = True
        for k1,k2 in itertools.permutations(cur,2):
            if not ((k1,k2) in V or (k2,k1) in V):
                flag = False
                break
        if flag:
            ans = max(ans,len(cur))
    print(ans)
    return

def JOI7_E():
    R, C = LI()
    A = [LI()for _ in range(R)]
    loop = 2**R
    ans = 0
    for i in range(loop):
        rev = set()
        for j in range(R):
            if (1<<j)&i==(1<<j):
                rev.add(j)
        cur = 0
        for j in range(C):
            s = 0
            for k in range(R):
                if k in rev and A[k][j]==0:
                    s += 1
                elif (not k in rev) and A[k][j]==1:
                    s += 1
            cur += max(s,R-s)
        ans = max(ans,cur)
    print(ans)
    return

def square869120Contest4_B():
    N, K = LI()
    A = LI()
    ans = inf
    loop = 2**(N-1)
    for i in range(loop):
        look = set()
        for j in range(N-1):
            if (1<<j)&i==(1<<j):
                look.add(j+1)
        if len(look)<K-1:
            continue
        high = A[0]
        cur = 0
        flag = True
        for j in range(1,N):
            if not (j in look):
                if A[j]>high:
                    flag = False
                    break
            else:
                if high >= A[j]:
                    cur += (high - A[j] + 1)
                    high += 1
                else:
                    high = A[j]
        #print(look,cur)
        if not flag:
            continue
        ans = min(ans,cur)
    print(ans)
    return

def ABC145_C():
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    c = 0
    for x in itertools.permutations(X):
        cur = 0
        c += 1
        for i in range(N-1):
            cur += ((x[i+1][0]-x[i][0])**2 + (x[i+1][1]-x[i][1])**2)**0.5
        ans += cur
    ans /= c
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC145_C()

"""

"""

Submission status: Accepted

Solution code:
import math
N = int(input())
X = []
ans = 0
for i in range(N):
    x = list(map(int, input().split()))
    X.append(x)
for j in range(N):
    for k in range(N):
        Y = (X[j][0]-X[k][0])**2 + (X[j][1]-X[k][1])**2
        ans += math.sqrt(Y)*math.factorial(N-1)
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
import math

def CalcDistance(x1, y1, x2, y2):
	return ((x1-x2)**2 + (y1-y2)**2)**(1/2)

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

distance = 0
Town = range(N)
for Route in itertools.permutations(Town,N):
	for TownNum in range(N-1):
		distance += CalcDistance(x[Route[TownNum]], y[Route[TownNum]], x[Route[TownNum+1]], y[Route[TownNum+1]])

print(distance/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for trans in itertools.permutations(range(N)):
	distance = 0
	for i in range(1,N):
		ind_2, ind_1 = trans[i], trans[i-1]
		x2,y2 = XY[ind_2]
		x1,y1 = XY[ind_1]
		distance += ((x2-x1)**2 + (y2-y1)**2)**(1/2)

	ans += distance

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations
from math import sqrt
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i], Y[i] = inpl()
sum_ = 0
cnt_ = 0
for P in permutations(range(N)):
    cnt_ += 1
    for i in range(N-1):
        sum_ += sqrt(pow(X[P[i+1]]-X[P[i]], 2) + pow(Y[P[i+1]] - Y[P[i]], 2))

print(sum_/cnt_)

Submission status: Accepted

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

print(total / waru)

Submission status: Accepted

Solution code:
import math
n=int(input())
base = math.factorial(n-1)
p = []
for i in range(n):
    x,y=map(int,input().split())
    p.append((x,y))
# length = [[0 for i in range(n)] for j in range(n)]
l=0
for i in range(n):
    for j in range(i+1,n):
        l += math.sqrt((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)*base*2
print(l/math.factorial(n))

Submission status: Accepted

Solution code:
import math
import itertools


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


def length(P, p):
    total = 0
    for i in range(len(p)-1):
        total += dist(P[p[i]], P[p[i+1]])
    return total


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

print(sum([length(P, p)
           for p in itertools.permutations(range(N))]) / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
*ps, = (tuple(map(int, input().split())) for _ in range(n))

ret = 0
for perm in permutations(ps):
    it = iter(perm)
    p = next(it)
    for q in it:
        ret += ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5
        p = q


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


ret /= fact(n)

print(ret)

Submission status: Accepted

Solution code:
import math
import itertools

n=int(input())
town=[]
length=0
pattern=math.factorial(n)
for i in range(n):
    tmp=list(map(int,input().split()))
    town.append(tmp)
town_all=list(itertools.permutations(town))
for i in town_all:
    for j in range(n-1):
        x_length=(i[j+1][0]-i[j][0])**2
        y_length=(i[j+1][1]-i[j][1])**2
        length+=math.sqrt(x_length+y_length)

print(length/pattern)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

N = int(input())
co = [tuple(map(int, input().split())) for _ in range(N)]
total = 0
for path in permutations(range(N)):
    for i, j in zip(path[0:N - 1], path[1:]):
        total += ((co[i][0] - co[j][0]) ** 2 + (co[i][1] - co[j][1]) ** 2) ** 0.5
print(total / factorial(N))

Submission status: Accepted

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

import math
def distance(p1,p2):
  x1,y1 = p1
  x2,y2 = p2
  return math.sqrt((x1-x2)**2 + (y1-y2)**2)
  
ans = 0
for i in range(n):
  for j in range(n):
    ans += distance(pos[i],pos[j])
print(ans/n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
import math

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

total = 0


for path in permutations(range(N)):
    dist = 0
    for a,b in zip(path, path[1:]):
        dist += math.sqrt((xy[a][0] - xy[b][0])**2 + (xy[a][1] - xy[b][1])**2)
    total += dist

print(total / math.factorial(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import permutations
from math import factorial
def main():
    N = int(input())
    xy = [tuple(map(int,input().split())) for _ in range(N)]
    answer = 0
    for perm in permutations(list(range(N))):
        for i in range(N-1):
            answer += ((xy[perm[i+1]][1]-xy[perm[i]][1])**2 + (xy[perm[i+1]][0]-xy[perm[i]][0])**2)**(1/2)
    print(answer/factorial(N))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

d=[]
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    
    l = math.sqrt((route[i][0]-route[j][0])**2+(route[i][1]-route[j][1])**2)
    d.append(l)
    

print(sum(d)*(n-1)/(n*(n-1)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools


def solve(N: int, x: "List[int]", y: "List[int]"):
    indices = [i for i in range(N)]
    permutations = itertools.permutations(indices)

    distances = []
    for permutation in permutations:
        total_distance = 0
        for i in range(0, N - 1):
            f, t = permutation[i : i + 2]
            distance = ((x[t] - x[f]) ** 2 + (y[t] - y[f]) ** 2) ** 0.5
            total_distance += distance
        distances.append(total_distance)
    result = sum(distances) / len(distances)

    print(result)
    return


# 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:
n=int(input())
l=[[int(i) for i in input().split()] for j in range(n)]

d=[]
for i in range(n):
  for j in range(i):
    d.append(((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5)
print(sum(d)*(n-1)/len(d))

Submission status: Accepted

Solution code:
#n個の都市を好きな都市から出発してすべての都市を１度だけ訪れる最短時間
#全ての都市の組i,jについてi,jを結ぶ道がある

import itertools
n=int(input())
A=[]
for i in range(n):
  A.append(list(map(int,input().split())))
  
def kaijo(x):
  if x==1:
    return x
  return x*kaijo(x-1)

def dist(x,y):
  return ((A[x][0]-A[y][0])**2+(A[x][1]-A[y][1])**2)**(1/2)

DIST=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    DIST[i][j]=dist(i,j)
    
ans=[]   
for Q in itertools.permutations([i for i in range(n)]):
  t=0
  for i in range(n-1):
    t+=DIST[Q[i]][Q[i+1]]
  ans.append(t)
  
print(sum(ans)/kaijo(n))

Submission status: Accepted

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

print(total)

Submission status: Accepted

Solution code:
N = int(input())

XY = [tuple(map(int,input().split())) for i in range(N)]
from itertools import permutations
from math import hypot
sm = k = 0
for ptn in permutations(XY):
    k += 1
    for (x1,y1),(x2,y2) in zip(ptn,ptn[1:]):
        sm += hypot(x1-x2, y1-y2)
print(sm/k)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
P = []

for i in range(n):
    x, y = map(int, input().split())
    P.append([x, y])
c = 0
for i in itertools.permutations(range(n)):
    for j in range(len(i)-1):
        c += ((P[i[j]][0] - P[i[j+1]][0])**2 + (P[i[j]][1] - P[i[j+1]][1])**2)**(1/2)
k = 1
for i in range(1, n+1):
    k *= i
print(c/k)

Submission status: Accepted

Solution code:
import math
import itertools


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


def path_cost(path):
    path_cost = 0
    for coordinate_idx in range(len(path) - 1):
        distance = dist(path[coordinate_idx][0], path[coordinate_idx][1], path[coordinate_idx+1][0], path[coordinate_idx+1][1])
        path_cost += distance
    return path_cost


def average_distance(coordinates, n):
    paths = list(itertools.permutations(coordinates, n))
    distance = 0
    for path in paths:
        distance += path_cost(path)
    return distance / len(paths)


n = int(input())
coordinates = []

for _ in range(n):
    coord_input = input().split()
    coordinates.append((int(coord_input[0]), int(coord_input[1])))
    
print(average_distance(coordinates, n))

Submission status: Accepted

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

ans = 0
cnt = 0

for i in itertools.permutations(x):
    cnt += 1
    for j in range(len(i) - 1):
        ans += ((i[j][0] - i[j + 1][0])**2 + (i[j][1] - i[j + 1][1])**2)**0.5

print(ans / cnt)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=0
for places in itertools.permutations([i for i in range(n)]):
  for i in range(n-1):
    x1,y1=arr[places[i]]
    x2,y2=arr[places[i+1]]
    ans+=((x2-x1)**2+(y2-y1)**2)**0.5
for i in range(1,n+1):
  ans=ans/i
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt


def dis(i, j):
    ret = float((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)
    return sqrt(ret)


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

p = list(permutations(list(range(n))))
sums = 0

for i in p:
    for j in range(len(i) - 1):
        sums += dis(xy[i[j]], xy[i[j + 1]])

print(sums / len(p))

Submission status: Accepted

Solution code:
def conbi(n):
  count  = 1
  for i in range(1,n+1):
    count *= i
  return count
N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
  x[i],y[i] = map(int,input().split())
X = conbi(N)
leng = 0
for i in range(N):
  for j in range(N):
    if i != j:
      leng += (((x[i]-x[j])**2 + (y[i]-y[j])**2))**0.5
print(leng/N)

Submission status: Accepted

Solution code:
#python3
from math import sqrt
from itertools import permutations
def dist(ti, tj):
    return sqrt((ti[0]-tj[0])**2 + (ti[1]-tj[1])**2)

def main():
    n = int(input())
    towns = []
    for _ in range(n):
        x,y = map(int, input().split())
        towns.append((x, y))    
    p = [i for i in range(n)]
    len = 0
    cnt = 0
    for index in permutations(p):
        for i in range(n-1):
            len += dist(towns[index[i]], towns[index[i+1]])
        cnt += 1
    print(len/cnt) 
main()

Submission status: Accepted

Solution code:
from itertools import permutations


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


N = int(input())
cities = [tuple(map(int, input().split())) for _ in range(N)]
paths = list(permutations(range(N)))
total = 0

for path in paths:
    for i in range(len(path)-1):
        total += distance(cities[path[i]], cities[path[i+1]])

ans = total / len(paths)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

def d(i,j):
    return np.sqrt((X[i]-X[j])**2 + (Y[i]-Y[j])**2)

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

L = [int(i) for i in range(N)]

ways = list(itertools.permutations(L, N))
sum_l = []
for i in range(len(ways)):
    sum = 0
    for j in range(N-1):
        sum += d(ways[i][j], ways[i][j+1])
    sum_l.append(sum)

print(np.average(np.array(sum_l)))