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
n=int(input())
XY=[]
for i in range(n):
  x,y=map(int,input().split())
  XY.append((x,y))
ans=0

def dist(a,b):
  ax,ay=a
  bx,by=b
  return ((ax-bx)**2+(ay-by)**2)**0.5

import itertools
for c in itertools.combinations(range(n),2):
  ans+=dist(XY[c[0]],XY[c[1]])
ans=ans*2/n
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [[0, 0] for _ in range(n)]

for i in range(n):
  x, y = map(float, input().split())
  l[i][0] = x
  l[i][1] = y
#print(l)

import itertools
import math
seq = range(0, n)
seqs = list(itertools.permutations(seq))
ans = 0
for c in seqs:
  t = 0
  for i in range(len(c)-1):
    z1 = c[i]
    z2 = c[i+1]
    t += math.sqrt((l[z1][0] - l[z2][0])**2+(l[z1][1] - l[z2][1])**2)
  ans += t

print(ans/len(seqs))

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

import itertools as it

N=one_int()

zahyous = [ two_int() for i in range(N)]

all_sums = 0
t = list(it.permutations(zahyous,N))
for i in t:
    sums=0
    for j in range(len(i)-1):
        sums += ( (i[j][0]-i[j+1][0])**2 +(i[j][1]-i[j+1][1])**2 ) ** (1/2)
    all_sums += sums/len(t)

print(all_sums)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    x=[0]*N
    y=[0]*N
    for i in range(N):
        x[i],y[i]=map(int,input().split())
    kaijou=1
    for i in range(1,N+1):
        kaijou*=i
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans+=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
    print(ans*2/N)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
town = []
for _ in range(n):
    xy = list(map(float, input().split()))
    town.append(xy)
    
from itertools import permutations
from math import sqrt
orders = list(permutations(range(n)))
dist_sum = 0
for order in orders:
    for i in range(n-1):
        a = town[order[i]]
        b = town[order[i+1]]
        dist = sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]))
        dist_sum += dist
print(dist_sum/len(orders))

Submission status: Accepted

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

n = int(input())
x = []
y = []
for i in range(n):
    seg = input().split()
    x.append(float(seg[0]))
    y.append(float(seg[1]))

edges = n * (n - 1) / 2
frac = 1
for i in range(1, n + 1):
    frac *= i
mul = frac * (n - 1) / edges

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += dist(x[i], y[i], x[j], y[j])

print(ans * mul / frac)

Submission status: Accepted

Solution code:
import itertools
import math

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

dist = 0

for i in range(N):
    for j in range(N):
        dist += ((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5 

dist = dist/N

print(dist)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
#print(l)
ans=0
r=list(itertools.permutations([i for i in range(n)]))
for i in range(len(r)):
    r[i]=list(r[i])
    #print(r[i])
    for j in range(n-1):
        ans+=((l[r[i][j]][0]-l[r[i][j+1]][0])**2+(l[r[i][j]][1]-l[r[i][j+1]][1])**2)**(1/2)
A=1
for i in range(1,n+1):
    A*=i
#print(ans,A)
print(ans/A)

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)

sums = 0
for i in range(N-1):
    for j in range(i+1, N):
        sums += ((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5

ans = sums * (N-1) / (N*(N-1)/2)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())

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

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

ans = 0
for root in roots:
    #for i,j in enumerate(root, root[1:]):
    for d in range(1,N):
        i,j = root[d-1], root[d]
        ans += math.sqrt( (xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2 )

print(ans / math.factorial(N))

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
import math
N = int(stdin.readline().rstrip())
road = []
for _ in range(N):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    road.append((x,y))

dist = []
for i in itertools.permutations(road):
    d = 0
    for j in range(1,N):
        d += math.sqrt((i[j-1][0]-i[j][0])**2 +  (i[j-1][1]-i[j][1])**2)
    dist.append(d)

ans = sum(dist)/math.factorial(N)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


d = dict()
p_s = None
n = 0

def main():
    global p_s, n
    n = int(input())
    p_s = [list(map(int, input().split(' '))) for i in range(n)]
    
    perms = list(permutations([i for i in range(n)]))
    l = len(perms)
    ans = sum(map(p2d, perms)) / l
    print(ans)


def p2d(lst):
    ans = 0
    for i in range(n-1):
        ans += fd(lst[i], lst[i+1])
    return ans


def fd(i, j):
    if (i, j) in d:
        return d[(i, j)]
    else:
        _d = ((p_s[i][0] - p_s[j][0])**2 + (p_s[i][1] - p_s[j][1])**2)**0.5
        d[(i, j)] = _d
        return _d


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations


n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
n_idx = [i for i in range(n)]
n_idx_per = list(permutations(n_idx))
ans = 0
for idx in n_idx_per:
    for i in range(len(idx) -1):
        ans += ((x_y[idx[i]][0] - x_y[idx[i+1]][0]) ** 2 +\
            (x_y[idx[i]][1] - x_y[idx[i+1]][1]) ** 2) ** 0.5
print(ans / len(n_idx_per))

Submission status: Accepted

Solution code:
import sys
import math

N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]

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

ans=0
for i in range(N):
    for j in range(i):
        ans+=math.sqrt( abs(x[i]-x[j])**2 + abs(y[i]-y[j])**2 )

print(ans*2/N)

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
for _ in range(n):
    li = list(map(int, input().split()))
    x.append(li[0])
    y.append(li[1])
line = []
for i in range(n):
    for j in range(i+1, n):
        line.append(((x[i]-x[j])**2 + (y[i]-y[j])**2)**0.5)
ans = sum(line) * 2 / n
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import itertools


N = int(input())

Town = []

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

all_dist = []

for perm in list(itertools.permutations(range(N))):
    (pre_x, pre_y) = Town[perm[0]]
    dist = 0
    for i in perm[1:]:
        (x, y) = Town[i]
        dist += ((pre_x - x)**2+(pre_y - y)**2)**(1/2)
    all_dist.append(dist)

mean = sum(all_dist)/len(all_dist)
print(mean)

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque

N = int(readline())

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

total = 0

def dfs(score, last, rem):
    global total
    if len(rem) == 0:
        total = total + score
        return
    
    for n in rem:
        x = score + ((YX[last][0] - YX[n][0]) ** 2 + (YX[last][1] - YX[n][1]) ** 2) ** 0.5
        dfs(x, n, rem - {n})

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

s = set(range(N))
for n in s:
    dfs(0, n, s - {n})
print(total / n_fact)

Submission status: Accepted

Solution code:
from math import *

n = int(input())
l = []
s = []

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

for x in range(n):
    for y in range(x + 1, n):
        s.append(sqrt((l[x][0] - l[y][0]) ** 2 + (l[x][1] - l[y][1]) ** 2))
        
print(sum(s) * 2 / n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import math


def main():
  coods = [tuple(map(int, input().split())) for _ in range(int(input()))]
  dists = [[0] * len(coods) for _ in range(len(coods))]

  for i, j in itertools.product(range(len(coods)), repeat=2):
    d = math.sqrt((coods[i][0] - coods[j][0]) ** 2 + (coods[i][1] - coods[j][1]) ** 2)
    dists[i][j] = d
    dists[j][i] = d

  dist = sum(sum(v) / (len(v) - 1) for v in dists)

  print('{:.14f}'.format(dist - dist / len(coods)))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt, factorial
n = int(input())

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

perms = permutations(towns)

sum_dists = 0
for path in list(perms):
    for i in range(n-1):
        dist = sqrt((path[i+1][0] - path[i][0])**2 +
                    (path[i+1][1] - path[i][1])**2)
        sum_dists += dist

print(sum_dists / factorial(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from itertools import permutations

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

for i in range(n):
    v = list(map(int, input().split(" ")))
    ps.append(v)

indexes = [i for i in range(n)]
temp = 0
for order in permutations(indexes, n):
    i = 0
    prev = []
    for idx in order:
        x, y = ps[idx]
        if i > 0:
            temp += math.sqrt((x - prev[0]) ** 2 + (y - prev[1]) ** 2)
        prev = (x, y)
        i += 1
        
for i in range(1, n + 1):
    temp /= i
        
print(temp)

Submission status: Accepted

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

import numpy as np
X = np.array(X)

Mx = (X[:, 0].reshape(-1, 1) - X[:, 0].reshape(1, -1)) ** 2
My = (X[:, 1].reshape(-1, 1) - X[:, 1].reshape(1, -1)) ** 2
M = np.sqrt(Mx + My)

print((N - 1) * (np.sum(M) / (N ** 2 - N)))

Submission status: Accepted

Solution code:
import math

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

checked = [False]*N

def dfs(L, s):
    if len(L) == N:
        k = 0
        for i in range(len(L)-1):
            a1, b1 = XY[L[i]]
            a2, b2 = XY[L[i+1]]
            k += math.sqrt((a1-a2)**2+(b1-b2)**2)
        return s+k
    for i in range(N):
        if not checked[i]:
            checked[i] = True
            s = dfs(L+[i], s)
            checked[i] = False
    return s

ans = dfs([], 0)
for n in range(1, N+1):
    ans /= n
print(ans)

Submission status: Accepted

Solution code:

import itertools
import math

n = int(input())
xy_list = [ [ int(v) for v in input().split() ] for i in range(n) ]

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

ans = 0
for i in itertools.permutations(range(n),n):
    l = 0
    for j in range(n-1):
        px, py = xy_list[i[j+1]]
        qx, qy = xy_list[i[j]]
        l += math.hypot(px-qx,py-qy)
    ans += l
print(ans/total)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


#x,y = [int(i) for i in readline().split()]

n = int(input())
xy = [[int(i) for i in readline().split()] for i in range(n)]

from math import hypot

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

for i in range(n):
    for j in range(n):
        d[i][j] = hypot(xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]) 


#print(d)

from itertools import permutations

L = list(range(n))
ans = 0.0
for p in permutations(L,n):
    for i in range(n-1):
        ans += d[p[i]][p[i+1]]

from math import factorial
print(ans/factorial(n))

Submission status: Accepted

Solution code:
n = int(input())
from math import sqrt
points = []
for i in range(n):
  a,b = map(int,input().split())
  points.append([a,b])
res = 0
for i in range(n):
  for j in range(i+1,n):
    res += sqrt((points[j][1]-points[i][1])**2+(points[j][0]-points[i][0])**2)
print((res*2)/n)

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
d, r = 0, 0
for route in permutations(range(n)):
    r += 1
    for i in range(n - 1):
        xi, yi = xy[route[i]]
        xj, yj = xy[route[i + 1]]
        d += ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
print(d / r)

Submission status: Accepted

Solution code:

def main():
    from math import sqrt, factorial
    from itertools import permutations

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

    D = {}
    for i in range(N):
        x0, y0 = XY[i]
        for j in range(N):
            x1, y1 = XY[j]
            d = sqrt((x0 - x1) ** 2 + (y0 - y1)**2)
            D[(i,j)] = d

    d = 0
    for p in permutations(range(N)):
        for i, j in zip(p, p[1:]):
            d += D[(i, j)]

    print(d/factorial(N))

main()

Submission status: Accepted

Solution code:
from itertools import permutations
from math import sqrt
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
xy = [inpl() for _ in range(N)]
S = sum(sum(sqrt(sum((xy[p[i+1]][k]-xy[p[i]][k])**2 for k in range(2)))
        for i in range(N-1)) for p in permutations(range(N)))
M = 1
for i in range(2,N+1): M*=i
print(S/M)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
XY = LRI(N)

perm = list(itertools.permutations(XY))

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


print(ans / len(perm))

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
n = int(input())
pos = [[int(t[0]), int(t[1])]for t in [input().split() for i in range(n)]]
cand = [i for i in range(n)]
def saiki(c,p):
	if len(c) == 0:
		return 0
	ret = 0
	o = copy.copy(c)
	for t in c:
		o.remove(t)
		if p != None:
			ret += ((p[0]-pos[t][0])**2+(p[1]-pos[t][1])**2)**.5
		ret += saiki(o, pos[t])
		o.append(t)
	return ret/len(c)
print(saiki(cand, None))

Submission status: Accepted

Solution code:
import math
import itertools
n=int(input())
uselist=[i for i in range(1,n+1)]
inputlist=list(tuple(map(int,input().split())) for i in range(n))
use=list(itertools.permutations(uselist))

ans=0
for some in use:
    for i in range(n-1):
        ans+=math.sqrt((inputlist[some[i]-1][1]-inputlist[some[i+1]-1][1])**2+(inputlist[some[i]-1][0]-inputlist[some[i+1]-1][0])**2)
c=1
for j in use[0]:
    c*=j

print(ans/c)

Submission status: Accepted

Solution code:
import itertools
def dist(x,y):
    return ((x[0]-y[0])**2 + (x[1]-y[1])**2)**(1/2)
n = int(input())
def fact(n):
    if n == 1:
        return 1
    else:
        return n*fact(n-1)
data = [list(map(int,input().split()))for i in range(n)]
ans = 0
for v in itertools.permutations(data):
    for i in range(1,n):
        ans += dist(v[i],v[i-1])

print(ans/fact(n))

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
import itertools
import math
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    cities = [[int(i) for i in input().split()] for _ in range(n)]

    dist = lambda p1, p2: ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

    t = 0
    for permutation in itertools.permutations(cities, n):
        prev = permutation[0]
        for city in permutation:
            t += dist(prev, city)

    print(t / math.factorial(n))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
ans = 0
cnt = 0
for p in permutations(range(N)):
    path = 0
    for i in range(1,N):
        path += ((X[p[i]]-X[p[i-1]])**2+(Y[p[i]]-Y[p[i-1]])**2)**0.5
    ans += path
    cnt += 1
print(ans / cnt)

Submission status: Accepted

Solution code:
import math
N = int(input())
XY = []
for _ in range(N):
    XY.append(list(map(int,input().split())))
Dists = dict()
c = 0
ans = 0.
for i in range(N):
    for j in range(N):
        if i < j:
            ans += math.sqrt((XY[i][0]-XY[j][0])**2+(XY[i][1]-XY[j][1])**2)
            c += 1
print((ans/c)*(N-1))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = [LI() for _ in range(n)]
    def f(a,b):
        return (pow(a[0]-b[0],2) + pow(a[1]-b[1],2))**0.5

    s = 0
    c = 0
    for a in itertools.permutations(aa, n):
        c += 1
        t = 0
        for i in range(n-1):
            t += f(a[i],a[i+1])
        s += t

    return s / c


print(main())

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
    xy.append([int(j) for j in input().split()])
ans=0
import itertools
for l in itertools.permutations("01234567"[:n]): 
    for i in range(n-1):
        x=xy[int(l[int(i)])][0]-xy[int(l[int(i+1)])][0]
        y=xy[int(l[int(i)])][1]-xy[int(l[int(i+1)])][1]
        ans+=((x)**2+(y)**2)**0.5
import math
print(ans/(math.factorial(n)))

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
hoge = list(range(N))
# for v in itertools.permutations(hoge, N):
#     print(v)
zyunban = list(itertools.permutations(hoge, N))
zahyo = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for i in range(math.factorial(N)):
    tmp = zyunban[i]
    for i, j in enumerate(tmp):
        if i == 0:
            now_x, now_y = zahyo[j]
        else:
            ans += ((zahyo[j][0]-now_x)**2+(zahyo[j][1]-now_y)**2)**(1/2)
            now_x, now_y = zahyo[j]

print(ans/math.factorial(N))

Submission status: Accepted

Solution code:
import math

N = int(input())

pos_list = []

for i in range(N):
	pos_list.append(tuple(map(int, input().strip().split())))

dist_table = [[None] * N for i in range(N)]

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

total = 0
number = 0

def calc(perm, count, towns):
	global total, number
	if count == N:
		for i in range(N - 1):
			total += dist_table[perm[i]][perm[i + 1]]
		number += 1
	else:
		for i in range(N):
			if towns[i]:
				towns[i] = False
				perm[count] = i
				calc(perm, count + 1, towns)
				towns[i] = True

calc([None for _ in range(N)], 0, [True for _ in range(N)])

print(total / number)

Submission status: Accepted

Solution code:
import itertools
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        xy = [list(map(int, input().split())) for _ in range(N)]

        total_distance = 0
        cnt = 0
        for p in itertools.permutations(xy):
            distance = 0
            cnt += 1
            for i in range(1, N):
                distance += ((p[i - 1][0] - p[i][0]) ** 2 + (p[i - 1][1] - p[i][1]) ** 2) ** 0.5
            total_distance += distance
        print(total_distance / cnt)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
ans = 0
cnt = 0
for xys in list(itertools.permutations([inpl() for _ in range(N)])):
    tmp = 0
    for i in range(1,N):
        bx,by = xys[i-1]
        x , y = xys[i]
        tmp += math.sqrt((bx-x)**2 + (by-y)**2)

    ans += tmp
    cnt += 1

print(ans/cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
import math

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ans_list = []
for i in permutations(range(N)):
    ans = 0
    for j in range(N-1):
        ans += math.sqrt((XY[i[j]][0] - XY[i[j+1]][0])**2 + (XY[i[j]][1] - XY[i[j+1]][1])**2)
    ans_list.append(ans)
print(sum(ans_list)/len(ans_list))

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())

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

Submission status: Accepted

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

sum_dist = 0
cnt = 0
from itertools import permutations

for seq in permutations(a):
    cnt += 1
    for i in range(len(seq)-1):
        sum_dist += ((seq[i][0] - seq[i+1][0]) ** 2 + (seq[i][1] - seq[i+1][1]) ** 2)**0.5

print('{:.8f}'.format(sum_dist / cnt))

Submission status: Accepted

Solution code:
import math
n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
dis = 0
for i in range(n):
    for j in range(n):
        if j == i:
            continue
        else:
            dis += math.sqrt((c[i][0] - c[j][0])**2 + (c[i][1] - c[j][1])**2)

print(dis / n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding: utf-8
# Last Modified: 16/Nov/19 05:44:05 PM


import sys


def main():
    from math import factorial, sqrt
    from itertools import permutations

    n = int(input())
    arr = [get_array() for _ in range(n)]

    x = [i for i in range(n)]
    p = list(permutations(x))

    def dis(x1, y1, x2, y2):
        return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

    distance = 0
    for j in p:
        for i in range(1, len(j)):
            distance += dis(
                arr[j[i]][0], arr[j[i]][1], arr[j[i - 1]][0], arr[j[i - 1]][1]
            )
    print(distance / factorial(n))


get_array = lambda: list(map(int, sys.stdin.readline().split()))


get_ints = lambda: map(int, sys.stdin.readline().split())


input = lambda: sys.stdin.readline().strip()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline
N=int(input())
towns = list(list(map(int,input().split())) for _ in range(N))

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

print(2*distance_sum/N)

Submission status: Accepted

Solution code:
import math
import itertools
n=int(input())
k=[[int(j)for j in input().split()]for i in[0]*n]
l=list(itertools.permutations(range(n)))
s=0
for i in l:
    p=0
    i=list(i)
    for j in range(len(i)-1):
        p+=math.sqrt((k[i[j]][0]-k[i[j+1]][0])**2+(k[i[j]][1]-k[i[j+1]][1])**2)
    s+=p
print(s/len(l))

Submission status: Accepted

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

n =int(input())

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

distl = []
for i in range(n):
    for j in range(i+1,n):
        dist1 = (xyl[i][0] - xyl[j][0]) ** 2
        dist2 = (xyl[i][1] - xyl[j][1]) ** 2
        dist3 = (dist1 + dist2) ** (1/2)
        distl.append(dist3)


print(sum(distl)*2/n)

Submission status: Accepted

Solution code:
def f(a, b):
  return pow((a[0]-b[0])**2+(a[1]-b[1])**2, 1/2)

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

i=0
ans=0
for i in range(N):
    for j in range(N):
        if i==j:
            pass
        else:
            ans+=((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def distance(a,b):
    ans = (a[0]-b[0])**2 + (a[1] - b[1])**2
    return ans**(0.5)
from itertools import permutations
from math import factorial
n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int,input().split())))
ans = 0
for d in permutations(range(n)):
    for i in range(n-1):
        ans += distance(xy[d[i]],xy[d[i+1]])
print(ans/factorial(n))