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 os
import itertools
import numpy as np

class getStdin(object):
    @classmethod
    def get_int(cls):
        return int(input())

    @classmethod
    def get_ss_int(cls):
        return list(map(int, input().split()))

    @classmethod
    def get_na_int(cls):
        return np.array(list(map(int, input().split())))


class funcCls(object):
    @classmethod
    def leng(cls, x1, y1, x2, y2):
        return np.sqrt((x1 - x2)**2 + (y1-y2)**2)

    @classmethod
    def done(cls, n, a):
        ll = len(a)
        total = dict()
        for i in range(ll):
            for j in range(i+1, ll):
                tmp = cls.leng(a[i][0], a[i][1], a[j][0], a[j][1])
                try:
                    if total[i] is not None:
                        total[i][j] = tmp

                except:
                    dum = dict()
                    dum[j] = tmp
                    total[i] = dum

        p = list(itertools.permutations(range(ll)))
        ss = list()
        for bbb in p:
            length = 0
            for c in range(len(bbb)-1):
                if bbb[c] < bbb[c+1]:
                    l = bbb[c]
                    r = bbb[c+1]
                else:
                    l = bbb[c+1]
                    r = bbb[c]
                length += total[l][r]

            ss.append(length)

        print(sum(ss) / len(ss))
        return

if __name__ == '__main__':
    n = getStdin.get_int()
    a = list()
    for i in range(n):
        a.append(getStdin.get_ss_int())

    funcCls.done(n, a)

    os.sys.exit(0)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

for i in range(0,N-1):
    for j in range(i+1,N):
        L[i][j]=np.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
        L[j][i]=L[i][j]

S=0
for i in range(0,N):
    S+=sum(L[i])
print(S/N)

Submission status: Accepted

Solution code:
import math

N = int(input())
p = []
fac = math.factorial(N)
for _ in range(N):
    x, y = list(map(int, input().split()))
    p.append([x, y])

t = []
def dfs(a, b):
    if len(b) == N:
        return t.append(b)
    for i in range(len(a)):
        dfs(a[:i] + a[i+1:], b + [a[i]])
dfs(p, [])
total = 0
for i in range(len(t)):
    for j in range(len(t[i]) - 1):
        total += math.sqrt((t[i][j][0] - t[i][j+1][0]) ** 2 + (t[i][j][1] - t[i][j+1][1]) ** 2)
print(total / fac)

Submission status: Accepted

Solution code:
import itertools
import math

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


def length(a, b):
    return math.sqrt(
        (a[0]-b[0])**2 + (a[1]-b[1])**2
    )
# x = (0, 1, 2,)　のtuple


def root(x):
    a = 0
    for i in range(len(x)-1):
        a += length(town[x[i]], town[x[i+1]])
    return a

fs = tuple(itertools.permutations(w))

ans = 0
for f in fs:
    ans += root(f)

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

Submission status: Accepted

Solution code:
import math
def main():
    N=int(input())
    X=[]
    Y=[]
    total=0
    for _ in range(N):
        x,y=map(int,input().split())
        X.append(x)
        Y.append(y)
    for i in range(N):
        for j in range(i+1,N):
            a=(X[i]-X[j])**2
            b=(Y[i]-Y[j])**2
            total+=math.sqrt(a+b)

    print(float(total*2/N))
            
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# http://merom686.hatenablog.com/entry/20120914/1347615020 を参考にしました

import math

n = int(input())
x = [0]*n
y = [0]*n
h = [0]*n
s = [0]*n
a = 0

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


def calcdis(p):
    d = 0
    for i in range(len(p)-1):
        a = int(p[i])
        b = int(p[i+1])
        d += math.sqrt(math.pow(x[a]-x[b],2)+math.pow(y[a]-y[b],2))

    return d


def listup(d,history,stuck):
    global a
    if (d != 0):
        for i in range(n):
            if (history[i]) : continue
            history[i] = 1
            stuck[d-1] = str(i)
            listup(d-1,history,stuck.copy())
            history[i] = 0
    else:
        a += calcdis("".join(stuck))



def main():
    listup(n,h,s)
    print(a / math.factorial(n))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

s = 0
for i in range(N):
    for j in range(i):
        s += ((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2) ** (1/2)
        
ans = s * a * 2 / b
print(ans)

Submission status: Accepted

Solution code:
import math
b = 0
N = int(input().strip())
grid = []
for i in range(N):
    array = list(map(int, input().strip().split()))
    grid.append(array)

for box1 in grid:
    x1 = box1[0]
    y1 = box1[1]

    for box2 in grid:
        x2 = box2[0]
        y2 = box2[1]
        a = (x1 - x2) ** 2 + (y1 - y2) ** 2
        
        b +=math.sqrt(a)
print(b/N)

Submission status: Accepted

Solution code:
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)
import math
def distance(x,y,i,j):
    d = math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)
    return d
def length(x,y):
    l = 0
    for i in range(0,N):
        for j in range(0,N):
            l = l + distance(x,y,i,j)
    return l / N
print(length(x,y))

Submission status: Accepted

Solution code:
import math

N = int(input())
x = [0] * N
y = [0] * N
l = 0

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

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

n = math.factorial(N)
m = 2 * math.factorial(N-1)
print(l * m / n)

Submission status: Accepted

Solution code:
#Beginner COnetst 145 /2019/11/16
#Probrem A
import math
DEBUG = 0

def dist(pi,pj):
    if DEBUG:print(pi,pj)
    dx = pi[0] - pj[0]
    dy = pi[1] - pj[1]
    tmp = dx*dx + dy*dy
    result = math.sqrt(tmp)
    if DEBUG:print(result)
    return result

def sum(n,pos):
    total = 0
    for i in range(n-1):
        for j in range(i+1,n):
            if DEBUG:print(i,j)
            total += dist(pos[i],pos[j])
    return total

def calc(n,pos):
    return sum(n,pos)*2/n

n = int(input())
pos = [ [0,0] for i in range(n)]
for i in range(n):
    pos[i] = list(map(int, input().split()))
    if DEBUG:print(pos[i])
print(calc(n,pos))

Submission status: Accepted

Solution code:
import math
import statistics
import itertools

n = int(input())
xl = []
yl = []

for i in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)

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

dd = []
for m in itertools.permutations(range(n)):
    dsum = 0
    for i in range(n-1):
        ii = m[i]
        iii = m[i+1]
        dsum += d(xl[ii], yl[ii], xl[iii], yl[iii])
    dd.append(dsum)
ans = statistics.mean(dd)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
XY = []
for i in range(N):
    XY.append(list(map(int, input().split())))
XY = np.array(XY)
XY.reshape(N,2)

ans = 0.0
for i in range(N):
    for j in range(N):
        ans += np.sqrt(np.sum(np.square(XY[i]-XY[j])))
ans /= N

print(ans)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
lst=[i for i in range(n)]
ans=0
for h in itertools.permutations(lst):
    num=0
    for i in range(1,n):
        w=h[i-1]
        z=h[i]
        num+=((xy[w][0]-xy[z][0])**2+(xy[w][1]-xy[z][1])**2)**0.5
    ans+=num
k=1
for i in range(1,n+1):
    k*=i
print(ans/k)

Submission status: Accepted

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

def calc(xi,xj,yi,yj):
    return ((xi-xj)**2+(yi-yj)**2)**0.5

def calclen(list):
    s = 0
    for i in range(N-1):
        s += calc(city[list[i]][0],city[list[i+1]][0],city[list[i]][1],city[list[i+1]][1])
    return s

tmp = 0
permutations = list(itertools.permutations(range(N)))
for i in permutations:
    tmp += calclen(i)
print(tmp/math.factorial(N))

Submission status: Accepted

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

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

print(sum * 2 / n)

Submission status: Accepted

Solution code:
n=int(input())
d=[]
for _ in range(n):
    a,b=map(int,input().split(" "))
    d.append([a,b])
from math import sqrt,factorial
from itertools import permutations
sum=0
for i in permutations(d,n):
    for j in range(1,n):
        c=sqrt((i[j-1][0]-i[j][0])**2+(i[j-1][1]-i[j][1])**2)
        sum+=c
print(sum/factorial(n))

Submission status: Accepted

Solution code:
import numpy as np

import copy
import math


def DFS(i, li, D, reached, mv, summ):
    if reached[i]:
        return

    for j in li:
        reached[i] = True

        if all(reached):
            reached[i] = False
            summ[0] += mv
            return

        li0 = copy.deepcopy(li)
        li0.remove(j)
        mv += D[i, j]
        DFS(j, li0, D, reached, mv, summ)
        mv -= D[i, j]
        reached[i] = False



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

    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) 

    reached = [False] * N

    li = list(range(N))

    summ = [0, 0]
    for i in range(N):
        s = i
        mv = 0
        DFS(s, li, D, reached, mv, summ)

    print(summ[0]/math.factorial(N))

        

main()

Submission status: Accepted

Solution code:
import numpy as np
import copy

def kaijo(n):
    if n == 1:
        return n
    return n * kaijo(n-1)

def search(dist,x0,x):
    global res,N,pos
    if len(x)==0:
        res+=dist
        #print(dist)
        return
    #print(x)
    #print(x,x0)
    #xx=copy.deepcopy(x)

    for k in range(len(x)):

        # if k>=1:
        #     xx=x[:(k-1)]
        # else:
        #     xx=[]
        # xx.extend(x[k+1:])

        tmp=x.pop(k)
        search(dist+np.linalg.norm(x0-pos[tmp]),pos[tmp],x)
        #x.append(tmp)
        x.insert(k,tmp)


N=int(input())
def acinput():
    return list(map(int, input().split(" ")))

dist=0
pos=[]
for i in range(N):
    pos.append(np.array(acinput()))

res=0

x=list(range(N))
for k in x:
    xx=copy.deepcopy(x)
    del xx[k]
    search(0,pos[k],xx)

print(res/(kaijo(N)))

Submission status: Accepted

Solution code:
N=int(input())

x = []
y = []
for i in range(0,N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
def d(e,f,g,h):
  return ((g-e)**2+(h-f)**2)**(1/2)
sum=0
for i in range(0,N-1):
  for j in range(i+1,N):
    sum=sum+d(x[i],y[i],x[j],y[j])
import math
print(sum*2/N)

Submission status: Accepted

Solution code:
import math
from math import factorial

N = int(input())
Lx = []
Ly = []
for i in range(N):
    xtmp,ytmp = map(int,input().split())
    Lx.append(xtmp)
    Ly.append(ytmp)

cnt = 0
Sum = 0
for i in range(N):
    for j in range(i+1,N):
        cnt += math.sqrt( (Lx[i]-Lx[j])**2 + (Ly[i]-Ly[j])**2 )

Sum = factorial(N-1)*2*cnt/factorial(N)
print(Sum)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import itertools
import math
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
  x[i], y[i] = map(int, input().split())
  
city = range(N)
ret = 0

def cal(ind):
  dist = 0
  n1 = ind[0]
  for n2 in ind:
    if n1 == n2:
      continue
    dist += dis(n1, n2)
    n1 = n2
  return dist

def dis(n1, n2):
  return np.sqrt((x[n1] - x[n2]) ** 2 + (y[n1] - y[n2]) ** 2)
  

for ind in itertools.permutations(city):
  ret += cal(ind)
print(ret / math.factorial(N))

Submission status: Accepted

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

d=0

for i in range(N):
  c=i+1
  for j in range(c,N):
    d+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
a=math.factorial(N)
print(d*2*(N-1)/(N*(N-1)))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
n1 = math.factorial(N)
athen = N - 1
henall =  n1 // (math.factorial(N - 2) * math.factorial(2))
#print(henall)

P = []
for i in range(N):
    P.append([int(j) for j in input().split()])
con1 = itertools.combinations(P, 2)

L = []
for j, k in con1:
    l = ((j[0]-k[0])**2 + (j[1]-k[1])**2)**0.5
    L.append(l)
#print(L)

times = (n1 * athen) // henall
#print(times)

aver = (sum(L) * times) / n1
print(aver)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
listA = []
total = 0
num = math.factorial(n)

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

listB = list(itertools.permutations(listA, n))

for i in range(len(listB)):
    for j in range(n-1):
        tmp = (listB[i][j][0] - listB[i][j+1][0])**2 + (listB[i][j][1] - listB[i][j+1][1])**2
        total += math.sqrt(tmp)
        
print(total/num)

Submission status: Accepted

Solution code:
import math as m
from statistics import mean

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


def dfs(j, lp, prev):
    # print("dpth: {}, lp:{}, prev:{}".format(j, lp, prev))

    k = len(lp)
    ll = []
    for j in range(k):
        lr = dfs(j+1, lp[0:j]+lp[j+1:k], lp[j])
        length = m.sqrt((lp[j][0]-prev[0])**2 + (lp[j][1] - prev[1])**2)
        if len(lr) == 0:
            ll.append(length)
        else:
            for p in range(len(lr)):
                lr[p] += length
            ll += lr

    # print(ll)
    return ll


gll = []

for i in range(n):
    gll += dfs(1, lp[0:i]+lp[i+1:n], lp[i])

print(mean(gll))

Submission status: Accepted

Solution code:
n=int(input())
points = []
for _ in range(n):
  k =[int(i) for i in input().split()]
  points.append(k)
#print(points)

total=0

for i in range(n):
  for j in range(i+1,n,1):
    x =(points[i][0]-points[j][0])**2
    y =(points[i][1]-points[j][1])**2
    total += (x+y)**(1/2)
    #print(i,j)
#print(total/7641.9817824387)
ave=total*2/n
print(ave)

Submission status: Accepted

Solution code:
import itertools
import math

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

dist = 0
for v in itertools.permutations(l):
    # print(v)
    ll = list(v)
    # print(ll)
    
    prev = None
    for lll in ll:
        # print(lll)
        
        if prev is not None:
            # print(prev)
            x1 = prev[0]
            y1 = prev[1]
            x2 = lll[0]
            y2 = lll[1]
            # print()
            a = math.sqrt(((x1 - x2) ** 2) + ((y1 - y2) ** 2))
            # print(a)
            dist += a
            # print(dist)
        
        prev = lll

print(dist / math.factorial(n))

Submission status: Accepted

Solution code:
import math
num = int(input())
townList = [list(map(int, input().split())) for i in range(num)]
drTown_2 = 0
for i in range(num):
	for j in range(num - i - 1):
		tmp = (townList[i][0] - townList[i + j + 1][0]) ** 2 + (townList[i][1] - townList[i + j + 1][1]) ** 2
		drTown_2 += tmp ** 0.5

print(drTown_2 * (num-1) * 2 / (num*(num-1)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import math
import itertools

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
A2 = list(itertools.combinations(A, 2))
A3 = [list(A2[_]) for _ in range(len(A2))]
length = 0
array1, array2, t_array = [], [], []

for x in range(len(A3)):
    t_array = A3[x]
    length = math.sqrt(pow(t_array[0][0] - t_array[1][0], 2) + pow(t_array[0][1] - t_array[1][1], 2))
    array1.append(length)

for k in range(len(array1) - 1):
    array2.append(array1[k] + array1[k + 1])
array2.append(array1[0] + array1[-1])
print(sum(array2) / N)

Submission status: Accepted

Solution code:
import math

N = int(input())

XY = [list(map(int, input().split())) for _ in range(N)]
X = [i[0] for i in XY]
Y = [i[1] for i in XY]

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

for i in range(N):
    for j in range(N):
        WS[i][j] = math.sqrt((X[i] - X[j])**2 + (Y[i] - Y[j])**2)

result = 0.0

for s in range(0, N-1):
    for d in range(s+1,N):
        result += WS[s][d]

print(2*result/(N))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


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


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    r = II()

    print(r*r)
    return

# B


def B():
    N = II()
    S = input()
    if len(S) % 2 == 0:
        print('No')
        return
    j = S[N//2]
    p = N//2
    for i in S[:N//2]:
        if i != j:
            print('No')
            return
        p += 1
        j = S[p]

    print('Yes')

    return

# C


def C():
    N = II()
    x = [0]*N
    y = [0]*N
    for i in range(N):
        x[i], y[i] = LI()
    ans = 0
    for j in range(N-1):
        for k in range(j+1, N):
            len = sqrt(((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k])))
            ans += len
    ans = ans*2/N
    print(ans)

    return

# D


def D():

    a, b, x = LI()
    BIG = a*a*b/2
    if x > BIG:
        y = 2*b-(2*x/a/a)
        print(math.degrees(math.atan(y/a)))
    else:
        y = 2*x/a/b
        print(math.degrees(math.atan(b/y)))
    return

# E


def E():
    N, K = LI()
    A = LI()
    F = LI()
    A.sort(reverse=True)
    F.sort()
    cost = []
    for i in range(len(N)):
        cost.append(A[i]*F[i])

    a = F[cost.index(max(cost))]

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    N = len(S)

    pass


# Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
import math

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += math.sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))

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

Submission status: Accepted

Solution code:
import itertools
N = int(input())
data_xy = [[ int(x) for x in input().split(" ")] for z in range(N)]
data_road = list(itertools.permutations(range(1,N+1), N))
sum_dis = float(0)
for i in data_road:
    for j in range(N-1):
        sum_dis += ((data_xy[i[j+1]-1][0] - data_xy[i[j]-1][0])**2 + (data_xy[i[j+1]-1][1] - data_xy[i[j]-1][1])**2)**0.5
mean_sum = sum_dis / len(data_road)
print('{:.10f}'.format(mean_sum))

Submission status: Accepted

Solution code:

from sys import stdin
n = int(stdin.readline().rstrip())
dis = []
for i in range(n):
    l = list(map(int, stdin.readline().rstrip().split()))
    dis.append(l)

def dist(x1,y1,xn,yn):
    di = ((x1-xn)**2 + (y1-yn)**2)**0.5
    return di

total = 0
for i in range(n-1):
    for j in range(i+1,n):
        d = dist(dis[i][0],dis[i][1],dis[j][0],dis[j][1])
        total += d

# nの階乗
ns = 1
for i in range(1,n+1):
    ns *= i

# 辺の数
num = 0
for i in range(n-1):
    num += 1 + i

ans = total * ((n-1)*ns)/num/ns

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math


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

p = list(itertools.permutations(XY_list))
length_sum = 0
for p_list in p:
    length = 0
    for i in range(len(p_list) - 1):
        length += math.sqrt((p_list[i + 1][0] - p_list[i][0])
                            ** 2 + (p_list[i + 1][1] - p_list[i][1]) ** 2)

    length_sum += length
print(length_sum / len(p))

Submission status: Accepted

Solution code:

import math

N=int(input())

L=[]
T=[]
for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

for i in range(N):
    for j in range(i+1,N):
        T.append(math.sqrt((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2))

print(sum(T)*(N-1)/len(T))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import itertools
a = int(input())
b = []


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


def calc_dist(l):
    r = 0
    for i in range(len(l)-1):
        r += dist(l[i],l[i+1])
    return(r)


for i in range(a):
    c = input().split()
    c[0],c[1] = int(c[0]),int(c[1])
    b.append(c)


r = 0

for l in list(itertools.permutations(b)):
    r += calc_dist(l)

print(r/math.factorial(a))

Submission status: Accepted

Solution code:
import math
n = int(input())
l = {}
for k in range(n):
  l.update({k: input().split()})
x = l.copy()
s = 0
c = 0
num = {
  2: 1,
  3: 3,
  4: 6,
  5: 10,
  6: 15,
  7: 21,
  8: 28
}
p = 0
while len(x) > 1:
  d = x.pop(c)
  for k,v in x.items():
    s = s + math.sqrt(
      pow(
        (int(d[0]) - int(v[0])), 2
      ) + pow(
        (int(d[1]) - int(v[1])), 2
      )
    )
    p = p + 1
  c = c + 1

print(s  * 2 / n)

Submission status: Accepted

Solution code:
import itertools
import numpy
import math

n = int(input())

seq = []
for _ in range(n):
  i = list(map(int, input().split(" ")))
  seq.append(i)
  
length = len(list(itertools.permutations(seq)))
results = []
paths = list(itertools.combinations(seq, 2))
factorial = math.factorial(n - 1)
for path in paths:
  a, b = path
  a = numpy.array(a)
  b = numpy.array(b)
  u = b - a
  results.append(numpy.linalg.norm(u) * (factorial * 2))
print(sum(results) / length)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())

x = []
y = []
l = []

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

sum_distance = 0
c = 0

for p in itertools.permutations(l):
    for i in range(n-1):
        sum_distance += ((x[p[i]]-x[p[i+1]])**2 + (y[p[i]]-y[p[i+1]])**2)**0.5

print(sum_distance/math.factorial(n))

Submission status: Accepted

Solution code:
a = [list(map(int, input().split())) for i in range(int(input()))]
from itertools import permutations as pss
from math import sqrt
b = list(pss(a))
sol = 0
for i in range(len(b)):
    for j in range(1, len(a)):
        x1 = b[i][j - 1][0]
        y1 = b[i][j - 1][1]
        x2 = b[i][j][0]
        y2 = b[i][j][1]
        sol += sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))
print(sol / len(b))

Submission status: Accepted

Solution code:
# coding UTF-8
# 
# problem C
# 
import itertools
import numpy as np
from scipy.spatial import distance

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

d = distance.cdist(city, city, metric='euclidean')

ans = []
city_no = list(range(N))
for elem in itertools.permutations(city_no, N):
    for j in range(len(elem)-1):
        ans.append(d[elem[j], elem[j+1]])

print((sum(ans)/len(ans))*(N-1))

Submission status: Accepted

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

import math
import itertools

# 入力
N = int(input())
list = []
for i in range(N) :
  a, b = map(int, input().split())
  list.append([a,b])

  
#for i in range(len(list)) :
  #print (str(list[i][0]) + " " + str(list[i][1]))

di = 0.0
S = 0.0
for v in itertools.permutations(list):
  #print (v)
  for ni in range(N-1) :
    
    if ni < N-1 :
      xi = v[ni][0]
      yi = v[ni][1]
      xj = v[ni+1][0]
      yj = v[ni+1][1]
    else :
      xi = v[ni][0]
      yi = v[ni][1]
      xj = v[0][0]
      yj = v[0][1]
      
    #print (xi, xj, yi, yj)
    #print ("xi-xj**2 " + str((xi - xj)**2) )
    #print str(((xi - xj)**2 + (yi - yj)**2) ** (1/2))
    di = math.sqrt((xi - xj)**2 + (yi - yj)**2)
    #print (di)
    S += di
    
print (S/math.factorial(N))
#print (math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

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


def cost_x(towns, i, j):
    return (towns[i][0] - towns[j][0]) ** 2


def cost_y(towns, i, j):
    return (towns[i][1] - towns[j][1]) ** 2


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

costs = 0
for i in range(0, len(towns)):
    for j in range(0, len(towns)):
        cost = 0
        if i == j:
            continue
        else:
            xs_cost = cost_x(towns, i, j)
            ys_cost = cost_y(towns, i, j)
            costs += math.sqrt((xs_cost + ys_cost))

print(costs/n)

Submission status: Accepted

Solution code:
import math
import itertools

def load_calc(pat):
    global N
    global pos_data
    
    dist = 0
    for i in range(N-1):
        dist += math.sqrt((pos_data[pat[i]][0]-pos_data[pat[i+1]][0])**2 + (pos_data[pat[i]][1]-pos_data[pat[i+1]][1])**2)
    
    return dist


seq = list()
pos_data = list()

N = int(input())
for i in range(N):
    xy = input().split()
    xy_i = [int(s) for s in xy]
    pos_data.append(xy_i)
    seq.append(int(i))


junretu = list(itertools.permutations(seq))
m = math.factorial(N)

total = 0
for j in range(m):
    total += load_calc(junretu[j])

print(total/m)

Submission status: Accepted

Solution code:
import itertools, math

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

p = 0
q = 0
for tpl in itertools.permutations(range(n)):
    total = 0
    for i in range(n - 1):
        total += math.hypot(x[tpl[i]] - x[tpl[i + 1]], y[tpl[i]] - y[tpl[i + 1]])
    p += total
    q += 1
print(p / q)

Submission status: Accepted

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

import itertools
import math

D = list(itertools.permutations(L, 2))
R = []
for i in range(len(D)):
    length = ((D[i][0][0] - D[i][1][0])**2 + (D[i][0][1] - D[i][1][1])**2)**0.5
    for j in range(math.factorial(N-1) * 2):
        R.append(length)

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

Submission status: Accepted

Solution code:
from statistics import mean
def calc(way, city, result, dist_map):
    i_city=list(city)
    if len(city)==0:
        dis=0
        for i in range(1,num):
            if way[i-1]<way[i]:
                dis+=dist_map[way[i-1]][way[i]-way[i-1]-1]
            else:
                dis+=dist_map[way[i]][way[i-1]-way[i]-1]
        result.append(dis)
    else:
        for i in i_city:
            n_way=list(way)
            n_city=list(city)
            n_way.append(i)
            n_city.remove(i)
            calc(n_way, n_city, result, dist_map)
num = int(input())
points = []
result = []
dist_map = []
for _ in range(num):
    points.append(tuple(map(float, input().split())))
for i in range(num-1):
    new=[]
    for j in range(i+1, num):
        new.append(((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)**0.5)
    dist_map.append(new)
way=[]
cite=list(range(num))
result=[]
calc(way, cite, result, dist_map)
print(mean(result))

Submission status: Accepted

Solution code:
import math
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
s=0
for j in range(n-1):
  for k in range(j+1,n):
    s += math.sqrt( (l[j][0]-l[k][0])**2 + (l[j][1]-l[k][1])**2 )

print(2*s/n)

Submission status: Accepted

Solution code:
import math
import numpy as np

n = int(input())
li = [[int(i) for i in input().split()] for _ in range(n)]
arr = np.array(li)

route = math.factorial(n)
div = route * 2 // n

tmp_index = np.arange(arr.shape[0])
xx, yy = np.meshgrid(tmp_index, tmp_index)
distances = np.linalg.norm(arr[xx]-arr[yy], axis=2)
print(np.sum(distances) / n)