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
N = int(input())
XY = []
for i in range(N):
  XY.append( list(map(int,input().split())) )

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
a =0 
for i in range(N-1):
  a+=combinations_count(N-2,i)*math.factorial(i)*math.factorial(N-2-i)
a *= 2
ans = 0
for i in range(N):
  for j in range(N):
    if i < j:
      x2 = (XY[i][0] - XY[j][0])**2
      y2 = (XY[i][1] - XY[j][1])**2
      ans +=  math.sqrt(x2+y2)  * a
print(ans/math.factorial(N))

Submission status: Accepted

Solution code:

# C
import itertools
import sys


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


n = int(input())

position = []
for _ in range(n):
    position.append(list(map(int, sys.stdin.readline().strip().split())))

distance = []
count = 0
for i in itertools.permutations(range(n)):
    for j in range(n - 1):
        distance.append(dist(position[i[j]], position[i[j + 1]]))
    count += 1

# print(count)
# print(distance)
print(sum(distance) / count)

Submission status: Accepted

Solution code:
N = int(input()) 
x = []
y = []

a = 1

for i in range(N):
    d = input().split()
    x.append(int(d[0]))
    y.append(int(d[1]))


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

count = 0
d = 0
for i in range(N):
    for j in range(N):
        if i == j:
            break

        d += distance(x[i], y[i], x[j], y[j])

print((d * (N - 1) / (N * (N - 1) / 2)))

Submission status: Accepted

Solution code:
import numpy as np
import math
n = int(input())
xy = [[int(i) for i in input().split()] for i in range(n)]
sum = 0
for i in range(n):
    for j in range(n):
        leng = ((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2)**0.5
        sum += math.factorial(n-1)*leng

print(sum/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math

n = int(input())
x_y = list(input().split() for i in range(n))
all = list(itertools.permutations(x_y))
l = 0
for i in all:
    for j in range(n-1):
        tmp = math.sqrt(math.pow(int(i[j][0])-int(i[j+1][0]), 2) + math.pow(int(i[j][1])-int(i[j+1][1]), 2))
        l += tmp

print(l/len(all))

Submission status: Accepted

Solution code:
import math

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

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

ans = 0
for i in range(N):
  for j in range(N):
    if j==i:
      continue
    ans += dist(S[i],S[j])
ans = ans / N

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
N=int(input())
M=N*(N-1)//2
X=np.array([list(map(int,input().split())) for _ in range(N)])
L=0
for i in range(N-1):
    for j in range(i+1,N):
        l=((X[i][0]-X[j][0])**2+(X[i][1]-X[j][1])**2)
        L+=np.sqrt(l)
print(L*2/N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from math import sqrt

def _s(): return sys.stdin.readline().strip()

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

def g(a):
    if len(a)==1:
        yield a
    else:
        for i in range(len(a)):
            ai = a[i]
            for aa in g(a[:i]+a[i+1:]):
                yield [ ai ] + aa
        

n = _i()
xy = [ _ia() for _ in range(n) ]

s = 0
c = 0
for a in g(xy):
    dist = 0
    prev = None
    for nxt in a:
        if prev:
            dist += sqrt( (prev[0]-nxt[0])**2 + (prev[1]-nxt[1])**2 )
        prev = nxt
    s += dist
    c +=1
#
print(s/c)

Submission status: Accepted

Solution code:
import math,itertools

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

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

sum = 0
for n in itertools.permutations(range(N)):
    for i in range(N-1):
        sum += dis[n[i]][n[i+1]]

print(sum/math.factorial(N))

Submission status: Accepted

Solution code:
import math


class Solution:
    def solve(self, n: int, points: list) -> int:

        s = 0.

        for i in range(n):
            p = points[i]
            for j in range(i+1, n):
                q = points[j]
                s += math.sqrt((p[0]-q[0])**2 + (p[1] - q[1])**2)

        return 2 * s / n


if __name__ == '__main__':

    # standard input
    n = int(input())
    points = []

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

    # solve
    solution = Solution()
    print(solution.solve(n, points))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
Cities = []
for _ in range(N):
  x, y = map(int,input().split())
  Cities.append([x, y])
seq = [i for i in range(N)]  
patterns = list(itertools.permutations(seq))
records = [0,0]

for item in patterns:
  for i in range(N-1):
    A = (Cities[item[i+1]][0] - Cities[item[i]][0])**2
    B = (Cities[item[i+1]][1] - Cities[item[i]][1])**2
    length = math.sqrt(A+B)
    records[0] += length
  records[1] += 1 
Answer = records[0]/records[1] 

print(Answer)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g
def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,m,g

def dijkstra(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n=inp()
    x=[]
    y=[]
    for _ in range(n):
        a,b=inpm()
        x.append(a)
        y.append(b)
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            cnt+=( (x[i]-x[j])**2 + (y[i]-y[j])**2 )**(1/2)
    com=1
    for i in range(1,n+1):
        com*=i
    s=(n*(n-1))//2
    print( (cnt*(n-1))/(s) )


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
b=int(input())
a=[]
aa=[]
n=0
i=0
while i<b:
    for x in input().split(" "):
        aa.append(float(x))
    a.append(aa)
    aa=[]
    i+=1
i=0
while i<b:
    j=0
    while j<b:
        if j!=i:
            n+=((a[i][0]-a[j][0])**2+(a[i][1]-a[j][1])**2)**0.5
        j+=1
    i+=1
print(n/b)

Submission status: Accepted

Solution code:
import itertools
import math

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

ans = 0
kazu_list = list(itertools.permutations(range(n)))
for nums in kazu_list:
    for i,num in enumerate(nums):
        if i < n-1:
            next_num = nums[i+1]
            ans += math.sqrt(pow((axis[num][0]-axis[next_num][0]),2) + pow((axis[num][1]-axis[next_num][1]),2))
print(ans/len(kazu_list))

Submission status: Accepted

Solution code:
import math
import itertools


N=int(input())
XY=[[None for _ in range(2)] for _ in range(N+1)]

for i in range(N):
    XY[i+1]=list(map(int,input().split()))

l = [_ for _ in range(1,N+1)]
p = itertools.permutations(l, N)
patern=math.factorial(N)

sums=0

for i in p:
    for j in range(N-1):
        sums+=math.sqrt((XY[i[j]][0]-XY[i[j+1]][0])**2 + (XY[i[j]][1] - XY[i[j+1]][1])**2) 

print(sums/patern)

Submission status: Accepted

Solution code:
from math import sqrt

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

total = 0.0
for i in range(N-1):
  for j in range(i+1, N):
    total += sqrt((P[i][0]-P[j][0])**2 + (P[i][1]-P[j][1])**2)

print(total * 2 / N)

Submission status: Accepted

Solution code:
import math
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)
total=[]
print(sum(d)*(n-1)/len(d))

Submission status: Accepted

Solution code:
import itertools
N=int(input())
r= [[int(i) for i in input().split()] for i in range(N)]
l=list(itertools.permutations(range(N)))
ans=[]
for i in range(len(l)):
    length_list=[]
    for j in range(N-1):
        length_list.append(((r[l[i][j]][0]-r[l[i][j+1]][0])**2+(r[l[i][j]][1]-r[l[i][j+1]][1])**2)**0.5)
    ans.append(sum(length_list))
print(sum(ans)/len(l))

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
N = int(stdin.readline().rstrip())
input = []
for i in range(N):
    input.append([int(x) for x in stdin.readline().rstrip().split()])

dist = 0
for ir in list(itertools.permutations(range(N))):
    now_dist = 0
    for i in range(len(ir) - 1):
        x = ir[i]
        y = ir[i + 1]
        now_dist += ((input[x][0] - input[y][0]) ** 2 + (input[x][1] - input[y][1]) ** 2) ** (1 / 2)
    dist += now_dist
output = dist / len(list(itertools.permutations(range(N))))
print(output)

Submission status: Accepted

Solution code:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans = int(ans)
    return ans


N=int(input())

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

kai=(math.factorial(N)*(N-1))//combi(N,2)

a=0

for i in range(N):
    for j in range(i+1,N):
        temp=((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5
        a+=temp*kai

print(a/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools

N = int(input())

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

results = 0
count = 0
for items in itertools.permutations(cities):
  count += 1
  length = 0
  for i in range(1, len(items)):
    length += ((items[i][1] - items[i-1][1])**2 + (items[i][0] - items[i-1][0])**2)**0.5
  results += length
print(results/count)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
p = []
ex = [1]
for i in range(8):
    ex.append(ex[i]*(i+1))

for i in range(n):
    p.append(list(map(int,input().split())))
l = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        l[i][j] = np.sqrt((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)
su = 0
ne = 1
for i in range(n):
    su = su + sum(l[i]) -l[i][i]
    ne = ne*(i+1)
print(ex[n-1]*2*(su/2)/ne)

Submission status: Accepted

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

sum = 0

def dist(x_1, y_1, x_2, y_2):
  return ((x_2 - x_1)**2 + (y_2 - y_1)**2)**0.5

for i in range(n):
  for j in range(i+1, n):
    sum += dist(x[i][0], x[i][1], x[j][0], x[j][1])
    
print(sum*2/n)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

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

sum = 0
for V in itertools.permutations(L, N):
	for i in range(N-1):
		sq = (X[V[i]][0] - X[V[i+1]][0])**2 + (X[V[i]][1] - X[V[i+1]][1])**2
		sum += (sq)**0.5

print(sum/Ns)

Submission status: Accepted

Solution code:
import math,itertools
def distance(i,j):
	return math.sqrt(math.pow(i[0]-j[0],2)+math.pow(i[1]-j[1],2))
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
city = []
for i in range(n):
	city.append([int(p) for p in input().split(' ')])
# print(n,city)

dists = [distance(c[0],c[1]) for c in itertools.combinations(city,2)]
t = math.factorial(n)/2*(n-1)/combinations_count(n,2)
# print(t)
res = sum([d*t for d in dists])/(math.factorial(n)/2)
print(res)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
A = []
for i in range(N):
    B = [int(i) for i in input().split()]
    A.append(B)
C = []
for i in range(N):
    C.append(i)
X = list(itertools.combinations(C,2))
LENGEs = []
for i in X:
    Y = A[i[0]]
    Z = A[i[1]]
    lenge = math.sqrt((Y[0] - Z[0]) ** 2 + (Y[1] - Z[1]) ** 2)
    LENGEs.append(lenge)
M = 0
for i in LENGEs:
    M += i
ans = (N-1 ) * (M / len(LENGEs))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
from math import sqrt

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

ite = list(itertools.permutations(data))
sum_num = 0
for D in ite:
	tmp = D[0]
	for i in range(1, N):
		sum_num += sqrt((tmp[0] - D[i][0]) ** 2 + (tmp[1] - D[i][1]) ** 2)
		tmp = D[i]

print(sum_num/len(ite))

Submission status: Accepted

Solution code:
from itertools import permutations as perm
n = int(input())
XY = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n):
	for j in range(n):
		if i == j:continue
		ab = XY[i]
		cd = XY[j]
		ans += ((ab[0]-cd[0])**2+(ab[1]-cd[1])**2)**0.5

print(ans/n)

Submission status: Accepted

Solution code:
import math

N = int(input())
xy = [list(map(int, input().split(' '))) for i in range(N)]
'''
dist = []
for i in range(N):
    dist.append([])
    for j in range(N):
        if i == j:
            dist[i].append(0)
            continue
        dist_x = (xy[i][0] - xy[j][0]) ** 2
        dist_y = (xy[i][1] - xy[j][1]) ** 2
        dist[i].append((dist_x + dist_y) ** 0.5)
print(*dist, sep='\n')
'''
sum = 0
bias = 2 * math.factorial(N-1)
for i in range(N-1):
    for j in range(i + 1, N):
        dist_x = (xy[i][0] - xy[j][0]) ** 2
        dist_y = (xy[i][1] - xy[j][1]) ** 2
        #print((dist_x + dist_y) ** 0.5)
        sum += ((dist_x + dist_y) ** 0.5) * bias
print(sum/math.factorial(N))

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
Sum = 0.0
for i in range(N):
    for j in range(N-i-1):
        Sum += ((X[i]-X[j+i+1])**2+(Y[i]-Y[j+i+1])**2)**0.5

print(Sum*2/N)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(float,input().split()))for i in range(N)]
sum = 0
for i in range(N-1):
    for j in range(i+1,N):
        a = (xy[i][0]-xy[j][0])**2
        b = (xy[i][1]-xy[j][1])**2
        sum+= (a+b)**0.5
print(sum*2/N)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

NN = [[0] * N for _ in range(N) ]
ans = 0
for i in range(N):
    for j in range(i,N):
        ans += (((x[i] - x[j]) ** 2 +(y[i] - y[j]) ** 2) ** (1/2)) * 2 
ans = ans / N

print(ans)

Submission status: Accepted

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

def solve(p, L):
    #print(p, L)
    if p and len(L) == 1:
        return ((L[0][0] - p[0])**2 + (L[0][1] - p[1])**2) ** 0.5
    result = 0
    for i in range(len(L)):
        result += solve(L[i], L[:i] + L[i+1:]) 
        if p:
            result += ( ((L[i][0] - p[0])**2 + (L[i][1] - p[1])**2) ** 0.5 ) * factorial(len(L)-1)
    return result

def factorial(n):
    a = 1
    for i in range(2, n+1):
        a *= i
    return a

ans = solve(None, xy)

M = factorial(N)
print(ans / M)

Submission status: Accepted

Solution code:
#input
N = int(input())
A = [[int(j) for j in input().split()] for i in range(N)]

length = []

l = 0
for i in A:
    for j in A:
        if i == j:
            continue
        l += (((j[0] - i[0])**2 + (j[1] - i[1])**2)**0.5)
        for k in A:
            if j == k or i == k:
                continue
            l += (((k[0] - j[0])**2 + (k[1] - j[1])**2)**0.5)
        length.append(l)
        l = 0

print(sum(length)/len(length))

Submission status: Accepted

Solution code:
import itertools

N = int(input())
point = []
length = 0
average = 0

for _ in range(N):
    point.append(list(map(int, input().split())))
    
combo = list(itertools.permutations(point, N))

for i in combo:
    for j in range(N - 1):
        average += ((i[j][0] - i[j+1][0])**2 + (i[j][1] - i[j+1][1])**2)**0.5
        
print(average / len(combo))

Submission status: Accepted

Solution code:
import math

len=0
N = int(input())
P = [list(map(int,input().split())) for i in range(N)]
for i in range(N-1):
  for j in range(i+1,N):
    len+=math.sqrt((P[i][0]-P[j][0])**2+(P[i][1]-P[j][1])**2)
    
print(2*len*math.factorial(N-1)/math.factorial(N))

Submission status: Accepted

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

Submission status: Accepted

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

for j in range(N):
    x1 = xlist[j][0]
    y1 = xlist[j][1]
    for k in range(j+1,N):
        x2 = xlist[k][0]
        y2 = xlist[k][1]
        di = math.sqrt((x1-x2)**2 + (y1-y2)**2)
        dist[j][k] = di

ans = 0


for i in range(N):
    ans += sum(dist[i])

ans = 2 *ans /N 

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

sums = 0.0
for perm in list(itertools.permutations(list(range(N)))):
    bef = perm[0]
    for i in perm[1:]:
        itoj = math.sqrt((xy[bef][0] - xy[i][0])**2 + (xy[bef][1] - xy[i][1])**2)
        sums += itoj
print(sums/math.factorial(N))

Submission status: Accepted

Solution code:
import math
import itertools
N=int(input())
kai=math.factorial(N)
li=[list(map(int,input().split())) for _ in range(N)]
a=0
for v in itertools.permutations(li,2):
    x=(v[0][0]-v[1][0])**2
    y=(v[0][1]-v[1][1])**2
    a+=math.sqrt(x+y)
print(a/N)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
x = []
y = []

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

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

d_ave = 0
for p in itertools.permutations(range(n)):
    d = 0
    nx = x[p[0]]
    ny = y[p[0]]
    for i in p:
        d += math.sqrt((nx-x[i])**2+(ny-y[i])**2)
        nx = x[i]
        ny = y[i]
    d_ave += d
print(d_ave / bikkuri(n))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools
import math

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

    l = range(N)
    cnt = 0
    total = 0
    for v in itertools.permutations(l):
        sum = 0
        for i in range(N-1):
            idx1 = v[i]
            idx2 = v[i+1]
            sum += math.sqrt( (X[idx1]-X[idx2]) ** 2 + (Y[idx1]-Y[idx2]) ** 2)
        total += sum
        cnt += 1

    print(total/cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import math

road=0
for i in range(N):
  for j in range(N):
    distance=(A[i][0]-A[j][0])**2+(A[i][1]-A[j][1])**2
    road+=math.sqrt(distance)/2
    
path=2/N
print(road*path)

Submission status: Accepted

Solution code:
import math
import itertools



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

comb = list(itertools.permutations(range(N), 2))

# print(comb)

dis = []
for i,j in comb:
    x = machi[i][0] - machi[j][0]
    y = machi[i][1] - machi[j][1]

    di = math.sqrt(abs(x**2+y**2))
    dis.append(di)
# print(dis)
print(sum(dis)/N)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

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

for order in permutations(range(n), n):
    curX, curY = towns[order[0]]
    length = 0
    for o in range(1, n):
        nextTown = towns[order[o]]
        length += sqrt((nextTown[0] - curX) ** 2 + (nextTown[1] - curY) ** 2 )
        curX, curY = nextTown
    path_length_list.append(length)

ans = sum(path_length_list) / len(path_length_list)
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
X = list()
Y = list()
for i in range(N):
    x, y = list(map(int, input().split()))
    X.append(x)
    Y.append(y)

dis = 0

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

print(dis / N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt

n=int(input())
permlist = list(permutations(range(n)))
#print('permlist: {}'.format(permlist))

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

lengths = 0.0
for p in permlist:
    length = 0.0
    for _ in range(len(p)-1):
        i = p[_]
        j = p[_+1]
        #print('i: {} j:{}'.format(i,j))
        length += sqrt( (x[i]-x[j])**2 + (y[i]-y[j])**2 )
    #print('length: {}'.format(length))
    lengths += length

print(lengths/len(permlist))

Submission status: Accepted

Solution code:
import math
N=int(input())
X = [[int(i) for i in input().split()] for _ in range(N)]
 
v = 0
for i in range(N):
    for j in range(i+1, N):
        yz = [(y - z)**2 for y, z in zip(X[i], X[j])]
        v += math.sqrt(sum(yz))
print(2*v/N)

Submission status: Accepted

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

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

result = 0.0
sz = 0

for item in itertools.permutations(range(n)):
    sz += 1
    ct = 0
    for i in item:
        if ct == 0:
            prev = i
            ct += 1
            continue
        result += math.sqrt(math.pow(x[i][0]-x[prev][0], 2) + math.pow(x[i][1]-x[prev][1], 2))
        prev = i

print(result/sz)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, factorial
n = int(input())
cities = [list(map(int, input().split())) for _ in range(n)]

ans = 0

for p in permutations(range(n)):
    for c1, c2 in zip(p, p[1:]):
        x1, y1 = cities[c1]
        x2, y2 = cities[c2]
        d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        ans += d
print(ans / factorial(n))

Submission status: Accepted

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


D = 0
for i in range(N-1):
    for j in range(i+1,N):
        x1 = C[i][0]
        y1 = C[i][1]
        x2 = C[j][0]
        y2 = C[j][1]
        D += math.sqrt( (x1-x2)**2 + (y1-y2)**2 )

print(2*D/N)

Submission status: Accepted

Solution code:
import math

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

ans = 0

for i in range(n):
    for j in range(n):
        length = math.sqrt((li[i][0] - li[j][0]) ** 2 + (li[i][1] - li[j][1]) ** 2)
        ans += length

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

Submission status: Accepted

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

Submission status: Accepted

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

list1 = [list(map(int,input().split())) for i in range(n) ]
list2 = list(itertools.permutations(range(n)))
ans = 0.0
count = 0.0
i = 0
while True:
    if i >= math.factorial(n):
        break
    for j in range(n-1):
        try:
            a = (list1[list2[i][j+1]][0] - list1[list2[i][j]][0])**2
        except ZeroDivisionError:
            a = 0
        try:
            b = (list1[list2[i][j+1]][1] - list1[list2[i][j]][1])**2
        except ZeroDivisionError:
            b = 0
        count += math.sqrt(a+b)
    ans += count
    count = 0
    i += 1

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

Submission status: Accepted

Solution code:
import math

a=int(input())
b=[]
d=0.0
cnt=0

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

for i in range(a-1):
    for j in range(i+1, a, 1):
        cx=(b[i][0]-b[j][0])
        cy=(b[i][1]-b[j][1])
        cz=math.sqrt(cx*cx+cy*cy)
        d+=cz
        cnt+=1

print(d/cnt*(a-1))

Submission status: Accepted

Solution code:
n=int(input())
a=[[int(i) for i in input().split()] for m in range(n)]
import itertools
import math
p=list(itertools.permutations(range(n),n))
total=0
for i in p:
    tmp=0
    for j in range(n-1):
        x=(a[i[j]][0]-a[i[j+1]][0])**2+(a[i[j]][1]-a[i[j+1]][1])**2
        x=x**0.5
        tmp+=x
    total+=tmp
print(total/math.factorial(n))

Submission status: Accepted

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

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

def rsum_nC2(N):
    ret=0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            ret+=r(i,j)
    return ret/N/(N-1)

def solve(N: int, x: "List[int]", y: "List[int]"):
    print(rsum_nC2(N)*(N-1))

    return

x = [int()] * (8)  # type: "List[int]"
y = [int()] * (8)  # type: "List[int]"
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
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())

p = []

g = 1

for i in range(n):
    g *= (i+1)
    x, y = map(int, input().split())
    p.append((x, y))

d = [[0]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        dd = math.sqrt(pow(p[i][0]-p[j][0], 2)+pow(p[i][1]-p[j][1], 2))
        d[i][j] = dd
        d[j][i] = dd


def hoge(s, i, dd):
    if not s:
        return dd
    sum_ = 0
    for ss in s:
        v = s.copy()
        v.remove(ss)
        sum_ += hoge(v, ss, dd+d[i][ss])
    return sum_


res = 0
for ii in range(n):
    c = set(range(n))
    c.remove(ii)
    res += hoge(c, ii, 0)

print(res/g)

Submission status: Accepted

Solution code:
import math

n = int(input())

x = [0,0,0,0,0,0,0,0,0,0,0]
y = [0,0,0,0,0,0,0,0,0,0,0]
f = [0,0,0,0,0,0,0,0,0,0,0]

def distance(x1, y1, x2, y2):
	ff = float((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
	return math.sqrt(ff)

total = 0
num = 0

def dfs(now, pre, dis):
	global total 
	global num

	if (now == n+1):
		total += dis
		num += 1
		return 
	if (now == 1):
		for i in range(1, n+1):
			f[i] = 1
			dfs(now+1, i, dis)
			f[i] = 0
	else:		
		for i in range(1, n+1):
			if f[i] == 0:
				f[i] = 1
				dfs(now+1, i, dis+distance(x[pre], y[pre], x[i], y[i]))
				f[i] = 0




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

# print(x)
# print(y)

dfs(1, 0, 0)
# print(total)
# print(num)
print(round(total/num, 10))