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 sys

#input = sys.stdin.readline
import math
#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True


def main():
#    h,w,a,b = map(int, input().split())
    n = int(input())
    xy=[]
    for i in range(n):
        xy.append(list(map(int,input().split())))
    d = []
    for i in range(0,n-1):
        for j in range(i+1,n):
            d.append(math.sqrt((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2))
#    print(d)
    ave=n*(n-1)//2
    aveve=math.factorial(n)*(n-1)
    aveve2=aveve//ave
    ave2=sum(d)*aveve2/(math.factorial(n))
    print(ave2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
input = sys.stdin.readline

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

N = int(input())
c = 1
for n in range(1, N + 1):
    c *= n
ans = [0] * c
xy = [0] * N
for n in range(N):
    xy[n] = tuple([int(x) for x in input().strip().split()])

i = 0
for xy_ in permutations(xy, N):
    pos = -1
    pre = 0
    ans_ = 0
    for n in range(N):
        if pos == -1:
            pre = xy_[n]
        pos = xy_[n]
        ans_ += dist(pre[0], pre[1], pos[0], pos[1])
        pre = pos
    ans[i] += ans_
    i += 1

print(sum(ans) / c)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


import numpy as np
from itertools import permutations
from math import factorial
N = read_a_int()
zahyou = []
for _ in range(N):
    zahyou.append(read_ints())

zahyou = np.array(zahyou)
toori = factorial(N)
# print(toori)


def get_length(zahyou, keiro: list):
    zahyou1 = zahyou[keiro[:-1], :]
    zahyou2 = zahyou[keiro[1:], :]
    ret = np.linalg.norm(zahyou1 - zahyou2, axis=1).sum()
    return ret


ans = 0
for keiro in permutations(list(range(N))):
    ans += get_length(zahyou, keiro) / toori

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from math import factorial

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

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

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

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial
N = int(input())
city = [list(map(int,input().split())) for i in range(N)]
result = 0
for v in permutations(city):
  for c in range(1, N):
    result += ((v[c-1][0] - v[c][0]) ** 2 + (v[c-1][1] - v[c][1]) ** 2) ** 0.5
print(result / factorial(N))

Submission status: Accepted

Solution code:
from math import hypot
from math import factorial

n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
m = factorial(n - 1)
ret = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ret += hypot(a[i][0] - a[j][0], a[i][1] - a[j][1]) * m
print(ret / factorial(n))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


def main():
    N = read_int()
    A = [tuple(read_ints()) for _ in range(N)]
    print(solve(N, A))


def fact(x):
    f = 1
    while x > 1:
        f *= x
        x -= 1
    return f


def solve(N, A):
    s = 0.0
    f = fact(N)
    e = f * (N - 1) // (N * (N - 1) // 2)
    for i in range(N):
        for j in range(i + 1, N):
            s += math.sqrt((A[j][0] - A[i][0]) ** 2 + (A[j][1] - A[i][1]) ** 2)
    dprint(s, e, f)
    return (e * s) / f


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools


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

cnt = 0
dist = 0.0
for vx in itertools.permutations(vL):
    d = 0.0
    cnt += 1
    for x,y in zip(vx[:-1],vx[1:]):
        tA, tB = vC[x], vC[y]
        d += ((tA[0]-tB[0])**2 + (tA[1]-tB[1])**2)**.5
    dist += d

print(dist/cnt)

Submission status: Accepted

Solution code:
import itertools

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

all = list(itertools.permutations(x))
q=0
for i in range(len(all)):
    for j in range(n-1):
       q+= ((all[i][j][0]-all[i][j+1][0])**2+(all[i][j][1]-all[i][j+1][1])**2)**0.5

print(q/len(all))

Submission status: Accepted

Solution code:
import math
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
s = 0
for i in range(N):
    for j in range(i+1, N):
        xi, yi = XY[i]
        xj, yj = XY[j]
        s += (math.sqrt((xi-xj)**2 + (yi-yj)**2))
print(2*s/N)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

N=int(input())
T=[] # 町のリスト
lenlist=[] # 距離のリスト

for _ in range(N): # 各町について
    t=list(map(int,input().split(" ")))
    T.append(t)

# 各順列について
for p in list(permutations(T,N)):
    lsum=0

    # 各町について、前後の距離を求める
    for pxi in range(1,len(p)):
        l=math.sqrt((p[pxi][0]-p[pxi-1][0])**2+(p[pxi][1]-p[pxi-1][1])**2)
        lsum+=l

    lenlist.append(lsum)

print(sum(lenlist)/len(lenlist))

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
xys = []
for i in range(n):
    x,y = words(int)
    xys.append((x,y))

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

fn = math.factorial(n)
nc2 = math.factorial(n) // (math.factorial(2) * math.factorial(n-2))

ans = 0
for i in range(n-1):
    for j in range(i,n):
        d = distance(xys[i][0], xys[i][1], xys[j][0], xys[j][1])
        ans += d * (fn // nc2)

print(ans*(n-1)/fn)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
X = [0] * N
Y = [0] * N
acc = 0
c = len(list(itertools.combinations(range(N), 2)))
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y
for p in itertools.permutations(range(N), 2):
    a = p[0]
    b = p[1]
    acc += ((X[a] - X[b]) ** 2 + (Y[a] - Y[b]) ** 2) ** (1/2)
print(acc/c*(N-1)/2)

Submission status: Accepted

Solution code:
import itertools
import math

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

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

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

seq = []
for i in range(N):
    seq.append(i)

sum1 = 0.0
for a in itertools.permutations(seq):
    for i in range(N-1):
        sum1 += distance(Data[a[i]], Data[a[i+1]])
print( sum1 / float(fact(N)))

Submission status: Accepted

Solution code:
import math
n = int(input())
p = []
dis = []
for i in range(n):
  x,y = map(int, input().split())
  p.append([x,y])
for i in range(n):
  for j in range(n):
    if i != j:
      dx = p[i][0] - p[j][0]
      dy = p[i][1] - p[j][1]
      dis.append(math.sqrt(dx*dx + dy*dy)/n)
print(round(sum(dis), 10))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations

input = sys.stdin.readline

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

ans = 0
npath = N*(N-1)
for i,j in permutations(range(N),2):
	dist = ( (xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2 )**0.5
	ans += dist/npath*(N-1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
path = []

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

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

total = 0.0

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

for p in permutations:
    for i in range(len(p) - 1):
        x1, y1 = path[p[i]]
        x2, y2 = path[p[i + 1]]
        d = distance(x1,y1,x2,y2)
        total += d

print(total / len(permutations))

Submission status: Accepted

Solution code:
import itertools

n=int(input())
div = 1
for i in range(1,n+1):
    	div*=i
xy = [[int(i) for i in input().split()] for i in range(n)]

_sum = 0

for _list in itertools.permutations([i for i in range(n)]):
	distance = 0
	for i in range(n-1):
    		distance += ((xy[_list[i]][0] - xy[_list[i+1]][0])**2 + (xy[_list[i]][1] - xy[_list[i+1]][1])**2)**0.5
	_sum += distance
print(_sum/div)

Submission status: Accepted

Solution code:
import itertools
import math

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    total = 0
    L = list(itertools.permutations(range(n), n))
    for l in L:
        l1, *la = l
        for i in la:
            total += ((A[l1][0]-A[i][0])**2 + (A[l1][1]-A[i][1])**2)**0.5
            l1 = i
    print(total/math.factorial(n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math

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

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

print(_sum/math.factorial(N))

Submission status: Accepted

Solution code:
import itertools
def sol():
    n=int(input())
    d=list(itertools.permutations([i for i in range(n)]))
    w=[]
    for i in range(n):
        x,y=map(int,input().split())
        w.append((x,y))
    ans=chk=0
    for i in d:
        for j in range(len(i)-1):
            ans+=((w[i[j]][0]-w[i[j+1]][0])**2+(w[i[j]][1]-w[i[j+1]][1])**2)**0.5
    print(ans/len(d))

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import math


def permutation(n, elems):
    if n == 0:
        return []
    elif n == 1:
        return [elems]
    else:
        result = []
        for q in elems:
            new_p = list(elems)
            new_p.remove(q)
            ac = permutation(n - 1, new_p)
            result += [[q] + a for a in ac]
        return result


def calc(N, xlist):
    d = {}
    for i in range(N):
        x = xlist[i]
        d[i] = {}
        for j in range(N):
            y = xlist[j]
            d[i][j] = math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)
    perms = permutation(N, list(range(N)))
    result = 0
    for p in perms:
        for i in range(N - 1):
            result += d[p[i]][p[i + 1]]
    result /= len(perms)
    return result


N = int(input())
x = [tuple(int(s) for s in input().split()) for _ in range(N)]
print(calc(N, x))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	xy = []
	seq = []

	for i in range(N):
		x,y = inputMap()
		xy.append((x,y))
		seq.append(i)

	ptns = list(itertools.permutations(seq))

	anss = []
	for ptn in ptns:
		ptn_list = list(ptn)

		strt = 0
		for i,val in enumerate(ptn_list):
			if i == 0:
				strt = val
				continue

			stx, sty = xy[strt]
			sdx, sdy = xy[val]
			tmptmp = ((stx-sdx)**2) + ((sty-sdy)**2)
			tmp = math.sqrt(tmptmp)
			anss.append(tmp)

	ans = 0
	for i in anss:
		ans += i

	print(ans/len(ptns))




if __name__ == "__main__":
	main()

Submission status: Accepted

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

N = int(input().split()[0])
xy_list = []

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

l = list(range(N))
p_list = list(itertools.permutations(l))
m_list = []
total = 0
count = 0
for p in p_list:
    count += 1
    t = 0
    for i, a in enumerate(p[:-1]):
        ax, ay = xy_list[a]
        bx, by = xy_list[p[i + 1]]
        t += ((ax - bx) ** 2 + (ay - by) ** 2) ** 0.5
    total += t

ans = total / count

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
X = []
Y = []
R = []

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

L = 0
cnt = 0

for r in list(itertools.permutations(R)):
    l = 0
    for i in range(N-1):
        l += ((X[r[i]] - X[r[i+1]])**2 + (Y[r[i]] - Y[r[i+1]])**2)**0.5
    L += l
    cnt += 1

print(L/cnt)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
listposi= []
order = []
for i in range(n):
    tmp = [int(j) for j in input().split()]
    listposi.append(tmp)
    order.append(i)
    
#print(listposi)
olist = list(itertools.permutations(order))
#print(olist)

dist = 0
for test in olist:
    for i in range(n-1):
        sta = test[i]
        gol = test[i+1]
        stax = listposi[sta][0]
        stay = listposi[sta][1]
        golx = listposi[gol][0]
        goly = listposi[gol][1]
        dist += ((stax-golx)**2+(stay-goly)**2)**0.5
print(dist/len(olist))

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt,factorial
n=int(input())
p=[tuple(map(int,input().split(' '))) for j in range(n)]
al = factorial(n)
ans = 0
l= [i for i in range(n)]
l=permutations(l)
for i in l:
    tmp = 0
    for j in range(n-1):
        tmp += sqrt((p[i[j]][0]-p[i[j+1]][0])**2+(p[i[j]][1]-p[i[j+1]][1])**2)
    ans += tmp/al
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

import itertools

arr = []

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


ptr = list(itertools.permutations(arr, n))


dis = 0

for i in range(len(ptr)):
    for j in range(n-1):
        dis +=((ptr[i][j][1]-ptr[i][j+1][1]) **2 + (ptr[i][j][0]-ptr[i][j+1][0])**2)**0.5
        
print(dis/len(ptr))

Submission status: Accepted

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

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

ans = 0
for i in range(n):
    x1, y1 = town[i]
    for j in range(n):
        if j == i:
            continue
        x2, y2 = town[j]
        dist = ((x1 - x2)**2 + (y1 - y2)**2) ** 0.5
        ans += dist

ans /= n
print(ans)

Submission status: Accepted

Solution code:
import math
def f(a,b):
    c = (a[0]-b[0])**2 + (a[1]-b[1])**2
    return math.sqrt(c)
n = int(input())
l = []
x = 0
for _ in range(n):
    l.append(list(map(int,input().split())))
for i in range(0,n-1):
    for j in range(i+1,n):
        x = x + f(l[i],l[j])
print((2*x)/n)

Submission status: Accepted

Solution code:
# coding:utf-8
import math
import itertools

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

ave = float(0)
cnt = 0
for r in itertools.permutations(l):
    tmp = float(0)
    for i in range(N-1):
        tmp += math.sqrt(((r[i][0] - r[i+1][0])**2) + ((r[i][1] - r[i+1][1])**2))
    ave += tmp
    cnt += 1
print(ave/cnt)

Submission status: Accepted

Solution code:
import itertools
import math
def dist(c1,c2):
  return math.sqrt((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)
n = int(input())
cities = {}
s = 0
for i in range(n):
  cities[i] = list(map(int,input().split()))
lis = [x for x in range(n)]
for junjo in itertools.permutations(lis):
  for i in range(len(junjo)-1):
#    print(i,cities[junjo[i]],cities[junjo[i+1]])
    s += dist(cities[junjo[i]],cities[junjo[i+1]])
print(s/math.factorial(n))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
sm = 0
xy= [list(map(int, input().split())) for _ in range(N)]
L = itertools.permutations(list(range(N)),N)
for l in L:
    for i in range(len(l)-1):
        sm += ((xy[l[i]][0]-xy[l[i+1]][0])**2+(xy[l[i]][1]-xy[l[i+1]][1])**2)**0.5

print(sm / math.factorial(N))

Submission status: Accepted

Solution code:
from itertools import permutations

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

def d(xy1, xy2):
    return ((xy1[0] - xy2[0])**2 + (xy1[1] - xy2[1])**2)**0.5

p = [i for i in permutations(xy, n)]

s, e = 0, 1
ds = []
for i in p:
    while e <= n-1:
        xy1 = i[s]
        xy2 = i[e]
        ds.append(d(xy1, xy2))
        s += 1
        e += 1
    s, e = 0, 1

print(sum(ds)/len(p))

Submission status: Accepted

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

mylist =[]

for i in range(N):
    myx , myy = map(int, input().split())
    mylist += [[myx, myy]]
    
#print(mylist)

mydis = []
mysum = 0
for i in range(N-1):
    for j in range(i+1,N):
        mysum += math.sqrt((mylist[i][0]-mylist[j][0]) **2 + (mylist[i][1]-mylist[j][1]) ** 2)
        #print(math.sqrt((mylist[i][0]-mylist[j][0]) **2 + (mylist[i][1]-mylist[j][1]) ** 2))
        

print((mysum*2)/(N))

Submission status: Accepted

Solution code:
import math

def main():

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

    f = 1
    for i in range(1, N+1): f *= i
    dist = [[0 for _ in range(N)] for _ in range(N)]
    d = 0
    for i in range(N):
        for j in range(N):
            dist[i][j] = math.sqrt(pow(p[i][0]-p[j][0], 2) + pow(p[i][1]-p[j][1], 2))
            d += dist[i][j]
    return d / N

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from itertools import combinations
def d(x1,x2):
    return ((x1[0]-x2[0])**2+(x1[1]-x2[1])**2)**0.5
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
tot = 0
for x in combinations(range(N),2):
    tot += d(A[x[0]],A[x[1]])
print(2*tot/N)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
lst = []
for i in range(N):
    x, y = map(int, input().split())
    lst.append([x, y])
dist = list(itertools.permutations(lst))
ans = []
for i in range(len(dist)):
    a = 0
    for j in range(N-1):
        a += ((dist[i][j][0]-dist[i][j+1][0])**2+(dist[i][j][1]-dist[i][j+1][1])**2)**0.5
    ans.append(a)
print(sum(ans)/len(ans))

Submission status: Accepted

Solution code:
N =int(input())
xy = [list(map(int,input().split())) for i in range(N)]
from itertools import permutations
res = []
for i in permutations(range(N)):
  s = 0
  for j in range(len(i)-1):
    xa,ya = xy[i[j]]
    xb,yb = xy[i[j+1]]
    s += ((xa-xb)**2+(yb-ya)**2)**(1/2)
  res += [s]
print(sum(res)/len(res))

Submission status: Accepted

Solution code:
n = int(input())

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

from itertools import permutations

res = 0
cnt = 0

for lst in permutations([i for i in range(n)], n):
    r = 0
    cnt += 1
    for i in range(n - 1):
        t1 = towns[lst[i]]
        t2 = towns[lst[i - 1]]
        r += ((t1[0] - t2[0]) ** 2 + (t1[1] - t2[1]) ** 2) ** 0.5

    res += r

print(res / cnt)

Submission status: Accepted

Solution code:
import itertools
N = int(input().strip())
C = [list(map(int, input().strip().split(' '))) for _ in range(N)]
ans = 0
def dist(t1, t2):
  return (((t1[0]-t2[0])**2) + ((t1[1]-t2[1])**2))**0.5

for i,j in itertools.combinations(range(N), 2):
  ans += dist(C[i], C[j])
ans = ans*2/N
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n = int(input())
l1 = []
l = []
ans = 0
for i in range(n):
    x,y = map(int,input().split())
    l.append(i)
    l1.append((x,y))
per = permutations(l)
for elm in per:
    for i in range(1,len(elm)):
        x=(((l1[elm[i]][0]-l1[elm[i-1]][0])**2)+((l1[elm[i]][1]-l1[elm[i-1]][1])**2))
        ans+=math.sqrt(x)
ans = ans/(math.factorial(n))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

dd = 0
patterns = list(itertools.permutations(list(range(n))))
for p in patterns:
    xd = 0
    for i in range(len(p) - 1):
        d = math.sqrt((x[p[i]] - x[p[i + 1]]) * (x[p[i]] - x[p[i + 1]]) + (y[p[i]] - y[p[i + 1]]) * (y[p[i]] - y[p[i + 1]]))
        xd += d
    dd += xd
print(dd / len(patterns))

Submission status: Accepted

Solution code:
import math
import itertools
N = int(input())
xy_list = []
for i in range(N):
    xy_list.append(list(map(int, input().split())))
distance = 0
count = 0
permutations = itertools.permutations(xy_list)
for permutation in permutations:
    count += 1
    for i in range(len(permutation) - 1):
        xi = permutation[i][0]
        yi = permutation[i][1]
        xj = permutation[i + 1][0]
        yj = permutation[i + 1][1]
        d = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
        distance += d
print(distance / count)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
#x, y = [], []
xy = []

for i in range(n):
    # v1, v2 = map(int, input().split())
    # x.append(v1)
    # y.append(v2)
    xy.append(list(map(int, input().split())))

perm = list(itertools.permutations(xy))
cnt = len(perm)

# print(len(perm))
# print(perm)
ans = 0
dis = 0

for i in range(cnt):
    for j in range(1, n):
        prevX = perm[i][j-1][0]
        prevY = perm[i][j-1][1]
        x = perm[i][j][0]
        y = perm[i][j][1]
        dis += ((prevX-x)**2 + (prevY-y)**2)**0.5

print(dis/len(perm))

Submission status: Accepted

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect

def dictCount(str):
    dict = {}

if __name__ == '__main__':
    n = int(input())
    s = []
    sum =0
    for i in range(n):
        a = [int(i) for i in input().split()]
        s.append(a)
    for i in range(n):
        for j in range(n):
            if j > i:
                x = s[i][0] -s[j][0]
                y = s[i][1] -s[j][1]
                sum = sum + math.sqrt(x*x + y*y)
    sum = sum*2

    print(sum/n)

Submission status: Accepted

Solution code:
import math

N = int(input())

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

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.spatial import distance

n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append([x, y])
dist_M = distance.cdist(xy, xy, metric='euclidean')
print(np.sum(dist_M)/(n))

Submission status: Accepted

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
avg = 0
d_sum = 0
for i in range(n-1):
  for l in range(i+1,n):
    d = math.sqrt((x_y[i][0]-x_y[l][0])**2 + (x_y[i][1]-x_y[l][1])**2)
    d_sum += d
k = (math.factorial(n) * (n-1))//combinations_count(n, 2)
avg = d_sum*k/math.factorial(n)
print(avg)

Submission status: Accepted

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

def distance(p):
    dst = 0
    for i in range(n-1):
        x1 = xval[p[i]]
        y1 = yval[p[i]]
        x2 = xval[p[i+1]]
        y2 = yval[p[i+1]]
        dst += d(x1,y1,x2,y2)
    return dst

def permutation(lst): 
    if len(lst) == 0: 
        return [] 
    if len(lst) == 1: 
        return [lst] 
    l = [] 
    for i in range(len(lst)): 
       m = lst[i] 
       remLst = lst[:i] + lst[i+1:] 
       for p in permutation(remLst): 
           l.append([m] + p) 
    return l 

n = int(input())

xval = []
yval = []

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

r = [i for i in range(n)]

per = permutation(r)

dist = []

for p in per:
    dist.append(distance(p))

print(sum(dist)/len(dist))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
x, y, r = [], [], []
for i in range(n):
    xi, yi = na()
    for xj, yj in zip(x, y):
        r.append(((xi - xj)**2 + (yi - yj)**2)**0.5)
    x.append(xi)
    y.append(yi)
print((sum(r)/len(r))*(n-1))

Submission status: Accepted

Solution code:
import itertools

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

def dist(perm):
    d = 0
    x0, y0 = X[perm[0]]
    for i in perm[1:]:
        x1, y1 = X[i]
        d += ((x1-x0)**2 + (y1-y0)**2)**0.5
        x0 = x1
        y0 = y1
    return d

def main():
    d = 0
    perms = list(itertools.permutations(range(N)))
    for perm in perms:
        d += dist(perm)
    return d/len(perms)

print(main())

Submission status: Accepted

Solution code:
import math
N = int(input())
x = []
y = []
for i in range(N):
  xi, yi = map(float, input().split())
  x.append(xi)
  y.append(yi)

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

print(2 * sum(l) / N)

Submission status: Accepted

Solution code:
import math
import itertools

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

for v in itertools.permutations(t, n):
    for i in range(len(v)-1):
        x = (v[i+1][0]-v[i][0])**2
        y = (v[i+1][1]-v[i][1])**2
        ans += math.sqrt(x + y)

print(ans/math.factorial(n))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
R = []
for _ in range(N):
    R.append(list(map(int, input().split())))
R = np.array(R)
X = R[:,0].reshape((-1,1))
Y = R[:,1].reshape((-1,1))
dX = X-X.T
dY = Y-Y.T
D = np.sqrt(dX*dX+dY*dY)
sum_D = np.sum(np.sum(D))/N
print(sum_D)

Submission status: Accepted

Solution code:
import math
import numpy as np
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
d = [[0 for _ in range(N)] for _ in range(N)]
s = 0
for i in range(N):
    for j in range(N):
        if i != j:
            xi,yi = xy[i]
            xj,yj = xy[j]
            d[i][j] = math.sqrt((xj-xi)**2+(yj-yi)**2)
print(np.sum(d)/ N)

Submission status: Accepted

Solution code:
import itertools
import math
n = int(input())
x = []
y = []
p = []
for i in range(n):
    src = list(map(int, input().split()))
    x.append(src[0])
    y.append(src[1])
    p.append(str(i))

length = 0
for i in itertools.permutations(p):
    for j in range(n - 1):
        pos0 = int(i[j])
        pos1 = int(i[j + 1])
        length += math.sqrt((x[pos1] - x[pos0]) ** 2 +
                            (y[pos1] - y[pos0]) ** 2)
ans = length / math.factorial(n)
print(ans)

Submission status: Accepted

Solution code:
import math

class Point:
	def __init__(self, x, y):
		self.x = x
		self.y = y

	def distance(self, other):
		return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)

if __name__ == "__main__":
	N = int(input())
	points = []
	d = 0
	for _ in range(N):
		x, y = map(int, input().split())
		q = Point(x, y)
		for p in points:
			d += q.distance(p)
		points.append(q)
	print(2.0 / float(N) * d)

Submission status: Accepted

Solution code:
from math import sqrt, factorial

if __name__ == "__main__":
    n = int(input())
    xy = list()
    for i in range(n):
        tmp = list(map(float, input().split()))
        xy.append(tmp)

    # まず2街間の距離を全部求める
    distance = list()
    for i in range(n):
        for j in range(n):
            if i is j:
                continue
            distance.append(
                sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2))

    ans = 0
    for d in distance:
        ans += d * factorial(n-1)

    print(ans / float(factorial(n)))