Координаталық жазықтықта $N$ қала бар. $i$-ші қала координаттарда орналасқан $(x_i,y_i)$ $i$ және $j$ қалалары арасындағы қашықтық мына формуламен есептеледі: $\sqrt{(x_i-x_j{)}^2+(y_i-y_j{)}^2}.$

Барлық қалаларды дәл бір рет аралайтын $N!$ түрлі жол бар. Жолдың ұзындығы — бірінші қаладан басталып, екінші, үшінші және соңғы қалаға дейінгі тікелей қашықтықтардың қосындысы. Барлық $N!$ жолдардың орташа ұзындығын есептеңіз

Енгізу

Бірінші жолда бір бүтін сан $N$ ($2\le N\le 8$) — қалалар саны. Келесі $N$ жолдың әрқайсысында екі бүтін сан $x_i$ және $y_i$ ($-1000\le x_i,y_i\le 1000$) — $i$-ші қаланың координаттары.

Шығару

Барлық жолдардың орташа ұзындығын басып шығарыңыз. Сіздің жауабыңыз төрешінің жауабынан ең көп дегенде ${10}^{-6}$ айырмашылықпен дұрыс болып саналады.

Бағалау жүйесі

Тапсырма 25 тесттен тұрады. Әрбір дұрыс орындалған тест үшін 4 балл беріледі.

Мысалдар бағаланбайды.

Мысалдар

Енгізу 1

3
0 0
1 0
0 1

Жауап 1

2.276142374915

Ескертпелер

Мүмкін болатын жолдар: $1\to 2\to 3,1\to 3\to 2,2\to 1\to 3,2\to 3\to 1,3\to 1\to 2,3\to 2\to 1.$