Problem:


Score : 300 points

Problem Statement

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

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

Constraints

2 \leq N \leq 8

-1000 \leq x_i \leq 1000

-1000 \leq y_i \leq 1000

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

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

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

2.2761423749

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

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

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

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

Sample Input 2

2
-879 981
-866 890

Sample Output 2

91.9238815543

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

Sample Input 3

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

Sample Output 3

7641.9817824387



Sample input:
3
0 0
1 0
0 1


Sample output:
2.2761423749

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append((x,y))
import itertools
import math
x=[i for i in range(n)]
s=list(itertools.permutations(x, n))
count=0
for item in s:
    for i in range(1,n):
        idx=item[i]
        pre=item[i-1]
        count+=math.sqrt((xy[idx][0]-xy[pre][0])**2+(xy[idx][1]-xy[pre][1])**2)
for i in range(1,n+1):
    count/=i
print(count)

Submission status: Accepted

Solution code:
import numpy as np
import math

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

def kyori(xi, yi, xj, yj):
    return np.sqrt((xi-xj)**2 + (yi-yj)**2)

goukei = 0
for i in range(n):
    for j in range(n):
        goukei += kyori(x[i],y[i],x[j],y[j])

print(goukei*math.factorial(n-1)/math.factorial(n))

Submission status: Accepted

Solution code:

import itertools
import math
N = int(input())
ps = list(itertools.permutations(range(N)))
sum_dist = 0

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

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

for p in ps:
    sum_val = 0.0
    for i in range(N-1):
        sum_val += dist(coos[p[i]], coos[p[i+1]])
    sum_dist += sum_val

print(sum_dist / len(ps))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):

    d = {}
    for i, j in combinations(range(N), r=2):
        xi, yi = XY[i]
        xj, yj = XY[j]
        d[(i, j)] = math.sqrt((xi-xj)**2 + (yi-yj)**2)

    ds = 0
    c = 0
    for p in permutations(range(N)):
        for k in range(1, N):
            i = min(p[k], p[k-1])
            j = max(p[k], p[k-1])
            ds += d[(i, j)]
        c += 1
    return ds/c


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

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

k = factorial(n)

ret = 0
for perm in permutations(xys):
    a, b = perm[0]
    for x, y in perm:
        ret += (((x - a) ** 2 + (y - b) ** 2) ** 0.5)
        a, b = x, y
print(ret / k)

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations
 
N = int(input())
x, y = zip(*(map(int, input().split()) for _ in range(N))) if N else ((), ())
 
ans = sum(
    sum(((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) ** 0.5 for i, j in zip(p, p[1:]))
    for p in permutations(range(N))
) / factorial(N)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dist(coords1,coords2):
    dx = coords1[0]-coords2[0]
    dy = coords1[1]-coords2[1]

    dx = dx**2
    dy = dy**2

    return (dx+dy)**0.5

def findDist(a, n,ans,coords):
    #print(a)
    for i in range(len(a)-1):
        ans[0] += dist(coords[a[i]-1],coords[a[i+1]-1])
    

def heapPermutation(a, size, n,coords,ans): 
    if (size == 1): 
        findDist(a, n,ans,coords) 
        return
  
    for i in range(size): 
        heapPermutation(a,size-1,n,coords,ans); 
        if size&1: 
            a[0], a[size-1] = a[size-1],a[0] 
        else: 
            a[i], a[size-1] = a[size-1],a[i]

def fact(n):
    count = 1
    for i in range(1,n+1):
        count *= i

    return count

def main():
    n = int(input())
    arr = []
    for i in range(1,n+1):
        arr.append(i)

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

    ans = [0]
    heapPermutation(arr,n,n,coords,ans)

    total = fact(n)

    #print(total)
    print(ans[0]/total)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
import itertools
from math import sqrt, factorial

def main():
    n = int(input().strip())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().strip().split())
    s = [0] * factorial(n)
    for k, perm in enumerate(itertools.permutations(range(n), n)):
        s[k] = 0
        for ind, i in enumerate(perm):
            if ind == 0:
                px, py = x[i], y[i]
                continue
            s[k] += sqrt((x[i] - px)**2 + (y[i] - py) ** 2)
            px, py = x[i], y[i]
    print(sum(s) / len(s))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
x = [list(map(int, input().split())) for i in range(N)]
sumx = 0

for i in range(N):
  for j in range(N):
    sumx += ((x[j][1] - x[i][1])**2 + (x[j][0] - x[i][0])**2) ** (1/2) 

ans = sumx / N
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

distance = []

for p in itertools.permutations(range(n)):
    for i in range(1,n):
        distance.append( ((P[p[i]][0]-P[p[i-1]][0])**2+(P[p[i]][1]-P[p[i-1]][1])**2)**(1/2) )

print(sum(distance)/math.factorial(n))

Submission status: Accepted

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))






def main():
    n = ii()
    xylist = []
    for i in range(n):
        xtmp,ytmp = mi()
        xylist.append([xtmp,ytmp])
    
    nf = f(n)
    dist = [ [] for i in range(n+1)]

    for i in range(n):
        for j in range(n):
            dist[i].append(sqrt(((xylist[i][0]-xylist[j][0])**2)+((xylist[i][1]-xylist[j][1])**2)))

    junbantmp = list(range(n))
    junban = list(itertools.permutations(junbantmp))

    ans = 0.0
    for jun in junban:
        distsum = 0.0
        for i in range(n-1):
            distsum += dist[jun[i]][jun[i+1]]
        ans+=distsum/nf
    
    print(ans)
        
    





main()

Submission status: Accepted

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

for _ in range(N):
    tmp = input().split()
    xy.append([int(tmp[0]), int(tmp[1])])

# print(xy)
sum = 0
for i in range(N - 1):
    xyi = xy[i]
    # print(xy[i])

    for j in range(i + 1, N):
        xyj = xy[j]

        sum += ((xyi[0]-xyj[0])**2 + (xyi[1]-xyj[1])**2)**(1/2)
        # print("\t" + str(xy[j]))

print("{:.10f}".format(2*sum/N))

Submission status: Accepted

Solution code:
from itertools import *

N = input()
x = [0.0]*N
y = [0.0]*N
for i in range(N):
  x[i], y[i] = map(float, raw_input().split())

s = 0.0
c = 0
for p in permutations(range(N)):
  for i in range(N-1):
    s += ((x[p[i+1]]-x[p[i]])**2+(y[p[i+1]]-y[p[i]])**2)**0.5
  c += 1
print "%.10f"%(s/c)

Submission status: Accepted

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

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

routeSum = 0
perm = list(permutations(i for i in range(n)))
for route in perm:
    for i in range(n-1):
        routeSum += sqrt( (x[route[i]] - x[route[i+1]])**2 + (y[route[i]] - y[route[i+1]])**2 )

print(routeSum/factorial(n))

Submission status: Accepted

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

def solve(N: int, x: "List[int]", y: "List[int]"):
    pattern = list(itertools.permutations(range(N)))
    sum_dist = 0
    for p in pattern:
        for i in range(1,N):
            sum_dist+=((x[p[i]]-x[p[i-1]])**2+(y[p[i]]-y[p[i-1]])**2)**(1/2)

    print(sum_dist/len(pattern))

    return


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:
# -*- coding: utf-8 -*-

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

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

print(ans / N)

Submission status: Accepted

Solution code:
import math
n=int(input())
L=[]

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

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

ans=0

for i in range(n-1):
    for q in range(i+1,n):
        ans+=dist(L[i],L[q])

ans/=n*(n-1)//2
ans*=n-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

seen=[]
dist=[]
d=0
def dfs(p):
  global d
  seen.append(p)
  if len(seen)==N:
    dist.append(d)
  else:
    for i in range(N):
      if i not in seen:
        d+=((xy[i][0]-xy[p][0])**2+(xy[i][1]-xy[p][1])**2)**0.5
        dfs(i)
        d-=((xy[i][0]-xy[p][0])**2+(xy[i][1]-xy[p][1])**2)**0.5
  seen.remove(p)
  
for j in range(N):
  dfs(j)
  
print(sum(dist)/Nkai)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
ans = 0
for I in itertools.permutations(range(N)):
    for i in range(N-1):
        ans += ((xy[I[i+1]][0]-xy[I[i]][0])**2+(xy[I[i+1]][1]-xy[I[i]][1])**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())
X = [list(map(int,input().split())) for i in range(N)]
l = [i for i in range(N)]
ans = 0
for v in itertools.permutations(l,N):
    for i in range(N):
        if i==0:x,y = X[v[i]]
        else:
            x2,y2 = X[v[i]]
            ans+=math.sqrt((x-x2)**2+(y-y2)**2)
            x,y = x2,y2
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
def c_average_length():
    from itertools import permutations
    from math import factorial
    N = int(input())
    Positions = [[int(i) for i in input().split()] for j in range(N)]

    ans = 0.0
    for route in permutations(range(N), N):
        tmp = 0.0
        for i in range(N - 1):
            cur_v = route[i]
            next_v = route[i + 1]
            tmp += ((Positions[next_v][0] - Positions[cur_v][0])**2 +
                    (Positions[next_v][1] - Positions[cur_v][1])**2)**0.5
        ans += tmp
    return ans / factorial(N)

print(c_average_length())

Submission status: Accepted

Solution code:
def main():
    def fact(n):
        if n == 0:
            return 1
        return n * fact(n-1)
    N = int(input())
    xy = [[int(i) for i in input().split()] for _ in range(N)]
    from math import hypot
    from itertools import permutations
    ans = 0
    for p in permutations(range(N)):
        for i in range(N-1):
            ans += hypot(xy[p[i]][0] - xy[p[i+1]][0],
                         xy[p[i]][1] - xy[p[i+1]][1])
    print(ans/fact(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())
grid = []
for i in range(N):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)

def l2(x1,y1,x2,y2):
    x = (x2 -x1)**2
    y = (y2 -y1)**2
    return math.sqrt(x+y)

len = 0

for i in range(N):
    for j in range(i,N):
        len += l2(grid[i][0],grid[i][1],grid[j][0],grid[j][1])

print((len*2/N))

Submission status: Accepted

Solution code:
import math

N = int(input())
position = [list(map(int, input().split())) for _ in range(N)]
S = 0
for i in range(N):
    x, y = position[i]
    for each_x, each_y in position:
        S += math.sqrt((x-each_x)**2 + (y-each_y)**2)

print(S/N)

Submission status: Accepted

Solution code:
import math

N = int(input())

x = [0] * N
y = [0] * N

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

dis = 0.0

for n1 in range(N-1):
    for n2 in range(n1 + 1, N):
        xd = x[n1] - x[n2]
        yd = y[n1] - y[n2]
        dis += math.sqrt(xd * xd + yd * yd)

print(dis * 2 / N)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
pers = permutations(p)
sums = 0
cnt = 0

for per in pers:
    cnt += 1
    sx, sy = per[0]
    for x, y in per:
        sums += sqrt((sx - x) ** 2 + (sy - y) ** 2)

print(sums / cnt)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from math import factorial, sqrt
from itertools import permutations
def main():
    N = int( input())
    V = [ tuple( map( int, input().split())) for _ in range(N)]
    ans = 0
    for P in permutations( range(N)):
        for i in range(N-1):
            ans += sqrt( (V[P[i]][0] - V[P[i+1]][0])**2 + (V[P[i]][1] - V[P[i+1]][1])**2)

    print( ans/ factorial(N))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
pos = []
for i in range(N):
    pos.append(tuple(map(int, input().split())))
total = 0
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = pos[i]
        x2, y2 = pos[j]
        total += ((x2-x1)**2 + (y2-y1)**2)**.5
print(total*2/N)

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n=int(input())
xy=[[int(i) for i in input().split()] for j in range(n)]
li=[]
for i in range(1,n+1):
    li.append(i)

ans = 0
for p in permutations(li):
    for i in range(1,len(p)):
        now = p[i]-1
        bef = p[i-1]-1
        ans+=((xy[now][0]-xy[bef][0])**2 + (xy[now][1]-xy[bef][1])**2)**0.5

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

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ls = []
    for i in range(n):
        x, y = list(map(int, readline().split()))
        ls.append([x, y])
    mt = 0
    cnt = 0
    for v in itertools.permutations([i for i in range(n)], n):
        cnt += 1
        for i in range(1, n):
            mt += ((ls[v[i-1]][0] - ls[v[i]][0]) ** 2 + (ls[v[i-1]][1] - ls[v[i]][1]) ** 2) ** 0.5
    print(mt / cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools, math
N = int(input())
d = [list(map(int,input().split())) for k in range(N)]
ans = 0
for e in itertools.permutations(d):
    temp = 0
    for k in range(len(e)-1):
        temp += math.sqrt((e[k][0] - e[k+1][0])**2 + (e[k][1] - e[k+1][1])**2)
    ans += temp
f = 1
for k in range(2,N+1):
    f *= k

print(ans/f)

Submission status: Accepted

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

cnt = 0
dist = 0
for i in range(n-1):
    xi, yi = city[i][0], city[i][1]
    for j in range(i+1, n):
        xj, yj = city[j][0], city[j][1]
        dist += ((xi - xj)**2 + (yi - yj)**2)**0.5
        cnt += 1

print(dist*(n-1)/cnt)

Submission status: Accepted

Solution code:
import itertools
import math
def dis(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
def main():
    N = int(input())
    l = []
    for _ in range(N):
        l.append(tuple(map(int, input().split())))
    n = [i for i in range(N)]
    total = 0
    for j in itertools.permutations(n):
        s = None
        e = None
        #d = 0
        for k in j:
            e = l[k]
            if s is None:
                s = e
                continue
            total += dis(s, e)
            s = e
    totaln = 1
    for i in range(2,N+1):
        totaln *= i
    return(total/totaln)
print(main())

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  xi,yi=map(int,input().split())
  x.append(xi)
  y.append(yi)
  
l=0
for i in range(n):
  for j in range(n):
    li=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
    l+=li
l/=n
print(l)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
cnt =[i for i in range(1,N+1)]
xy = [[int(x) for x in input().split()] for i in range(N)]
ans = 0
ansl = 0
cn = 0
for v in itertools.permutations(cnt):
  cn+=1
  for i in range(N-1):
    ans +=((xy[v[i+1]-1][0]-xy[v[i]-1][0])**2+(xy[v[i+1]-1][1]-xy[v[i]-1][1])**2)**0.5
print(ans/cn)

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
cities = [tuple(map(int, input().split())) for _ in range(N)]
# print(cities)


def dist(ci, cj):
    return ((ci[0]-cj[0])**2+(ci[1]-cj[1])**2)**0.5


ans = 0
for p in itertools.permutations(range(N), N):
    for i in range(N-1):
        ans += dist(cities[p[i]], cities[p[i+1]])
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    xy = []
    for _ in range(n):
        x, y = map(int, input().split())
        xy.append((x, y))
    dist = 0
    for j in range(n):
        x1, y1 = xy[j]
        for i in range(j):
            x0, y0 = xy[i]
            dist += ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5
    print(dist * 2 / n)

main()

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
n_ = 1
for i in range(n):
    n_ *= i+1
c = [tuple(map(int,input().split())) for _ in range(n)]
tot = 0

def dis(c,x,y):
  x1,y1 = c[x]
  x2,y2 = c[y]
  return ((x1-x2)**2 + (y1-y2)**2)**.5

for l in permutations(range(n)):
    d = 0
    cur = l[0]
    for x in l:
        d += dis(c,cur,x)
        cur = x
    tot += d/n_
print(tot)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def conb(n,r): 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = inp()
xy = [inpl() for i in range(n)]
res = 0
m = math.factorial(n)*(n-1)//conb(n,2)
for i in range(n):
    for j in range(i+1,n):
        tmp = math.sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)
        res += tmp*m
print(res/math.factorial(n))

Submission status: Accepted

Solution code:
from math import sqrt

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

result = 0
for i in range(N):
  for j in range(N):
    if i != j:
      result += sqrt((xy[i][0] - xy[j][0]) * (xy[i][0] - xy[j][0]) + (xy[i][1] - xy[j][1]) * (xy[i][1] - xy[j][1]))
print(result / N)

Submission status: Accepted

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

lst = []

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

ans = 0
for X, Y in lst:
    for x, y in lst:
        ans += math.sqrt((X - x) ** 2 + (Y - y) ** 2)

ans *= math.factorial(N - 1)

print (ans / math.factorial(N))

Submission status: Accepted

Solution code:
import itertools, math

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

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

print(dist/math.factorial(N))

Submission status: Accepted

Solution code:
import numpy as np
from math import sqrt
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
seki = 1
for i in range(N):
    seki *= (i + 1)


graph = np.zeros((N, N))
for i in range(N):
    for j in range(N):
        graph[i][j] = sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)

print(np.sum(graph) / 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)

goukei = 0
bunbo = 0
for junro in itertools.permutations(range(N)):
    bunbo += 1
    for i in range(len(junro)-1):
        goukei += ((X[junro[i]] - X[junro[i+1]]) ** 2 +
                   (Y[junro[i]] - Y[junro[i+1]]) ** 2) ** 0.5

print(goukei / bunbo)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

ans = 0

l = [int(i) for i in range(N)]
for P in itertools.permutations(l):
    for i in range(1, N):
        ans += ((L[P[i-1]][0]-L[P[i]][0])**2 + (L[P[i-1]][1]-L[P[i]][1])**2)**0.5
        
def f(n):
    if n == 0:
        return 1
    else:
        return n*f(n-1)
    
print(ans/f(N))

Submission status: Accepted

Solution code:
import math

n = int(input())

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

total = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        total += math.sqrt((pos[i][0] - pos[j][0]) ** 2 + (pos[i][1] - pos[j][1]) ** 2)

nroot = (n - 1) * n / 2 / (n - 1)
print(total / nroot)

Submission status: Accepted

Solution code:
from itertools import permutations


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


n = int(input())
li = {}
for i in range(n):
    a, b = map(int, input().split())
    if i + 1 not in li:
        li[i + 1] = [a, b]
res = [i for i in range(1, n + 1)]
res = list(permutations(res))
c = 0
for i in res:
    for j in range(len(i)-1):
        c += dist(li[i[j]], li[i[j + 1]])
print(c / len(res))

Submission status: Accepted

Solution code:
import math
import itertools

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

d = 0.0
for (x1,y1),(x2,y2) in itertools.permutations(xy_arr, 2):
    d += math.sqrt((x2-x1)**2+(y2-y1)**2)
d *= 1.0/N

print(d)

Submission status: Accepted

Solution code:
import math

n = int(input())
nodes = []
for i in range(n):
    nodes.append([int(x) for x in input().split(' ')])

sums = 0

for i in range(n):
    for j in range(n):
        if i != j:
            sums += math.sqrt((nodes[i][0] - nodes[j][0]) ** 2 + (nodes[i][1] - nodes[j][1]) ** 2)

print(sums / n)

Submission status: Accepted

Solution code:
import math
a=int(input())
b=[list(map(int,input().split())) for i in range(a)]
ans=0
def dist(i,j):
  return ((i[0]-j[0])**2+(i[1]-j[1])**2)**0.5

for i in range(a):
  for j in range(a):
    if i==j:
      continue
    else:
      ans+=dist(b[i],b[j])*math.factorial(a-1)
      
print(ans/math.factorial(a))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

import math
import itertools

def main():
    def calc(i, j):
        return math.sqrt((xs[i] - xs[j]) * (xs[i] - xs[j]) +(ys[i] - ys[j]) * (ys[i] - ys[j]))
    n = II()
    xs = []
    ys = []
    for i in range(n):
        x, y = LI()
        xs.append(x)
        ys.append(y)
    ans = 0
    list_ = list(itertools.permutations(list(range(n))))
    for i in list_:
        for j in range(n-1):
            ans += calc(i[j], i[j+1])
    print(ans / len(list_))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
xy = []
for i in range(N):
    tmp1, tmp2 = map(int,input().split())
    xy.append((tmp1,tmp2))
#print(xy)
d = np.zeros((N,N))
for i in range(N):
    for j in range(N):
        d[i][j] = np.sqrt((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)
print(np.sum(d)/N)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
import math
n = int(input())
ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    ls.append((x, y))

_sum = 0
for candi in permutations(range(n)):
    for i in range(n-1):
        cur = ls[candi[i]]
        _next = ls[candi[i+1]]
        _sum += math.sqrt((cur[0] - _next[0]) ** 2 + (cur[1] - _next[1]) ** 2)
print(_sum / math.factorial(n))

Submission status: Accepted

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

dis = 0
import itertools
import math
for per in itertools.permutations(range(n)):
  first = True
  for i in per:
    if not first:
      dis += math.sqrt((x[i] - x[previ]) ** 2 + (y[i] - y[previ]) ** 2)
    previ = i
    first = False

print(dis / math.factorial(n))

Submission status: Accepted

Solution code:
from itertools import permutations

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

ret = 0
for perm in permutations(range(N)) :
    for i in range(1, N) :
        cx, cy = xy[perm[i]]
        px, py = xy[perm[i-1]]
        
        ret += pow((cx - px) ** 2 + (cy - py) ** 2, 0.5)

x = 1
for i in range(1, N + 1) :
    x *= i
    
print(ret / x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools
import math
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template


def main():
    N = ii()
    L = list()
    for i in range(N):
        L.append(lmi())
    ans = 0.0
    for l in itertools.permutations(L, N):
        for i in range(N - 1):
            ans += math.sqrt((l[i + 1][0] - l[i][0])**2 + (l[i + 1][1] - l[i][1])**2)
    print(ans / math.factorial(N))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():  
    n = int(input())
    xy = [tuple(map(int,input().split())) for _ in range(n)]
    ans = 0
    c = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                x1 = xy[i][0]
                y1 = xy[i][1]
                x2 = xy[j][0]
                y2 = xy[j][1]
                ans += ((x1-x2)**2+(y1-y2)**2)**(1/2)
                c += 1
    print(ans*(n-1)/c)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
ans = 0
for s in permutations(range(n)):
    tmp = 0
    for i in range(n - 1):
        tmp += f(int(s[i + 1]), int(s[i]))
    ans += tmp
for i in range(n):
    ans /= i + 1
print(ans)