Problem D
Gini Stuðull

Árið 1912 gaf félagsfræðingurinn og tölfræðingurinn Corrado Gini út pappír titlaðan “Variability and Mutability”. Í honum kynnir hann til söguna hinn svokallaðan Gini stuðul. Markmið stuðulsins er að mæla ójöfnuð í dreifingum og er oft notaður til að mæla tekjuójöfnuð innan hópa. Stuðullinn tekur gildi milli $0$ og $1$, þar sem $0$ merkir fullkominn jöfnuð en $1$ fullkominn ójöfnuð. Sem dæmi hefur Ísland Gini stuðul upp á $0.256$ og Bandaríkin $0.415$.
Til þess að reikna stuðulinn fyrir hóp af fólki þarf að vita tekjur allra einstaklinga í hópnum. Ef $y_1, y_2, \ldots , y_ n$ ($y_ i > 0$ fyrir öll $i$) eru tekjur $n$ einstaklinga má reikna Gini stuðul þess hóps með eftirfarandi formúlu: \[ G = \dfrac { \sum \limits _{i=1}^ n \sum \limits _{j=1}^ n \lvert y_ i - y_ j \rvert }{ 2 \sum \limits _{i=1}^ n \sum \limits _{j=1}^ n y_ i } \]

Hér táknar $\lvert x\rvert $ algildi $x$: $\lvert x\rvert = x$ ef $x \geq 0$, en $\lvert x\rvert = -x$ ef $x < 0$.

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $n$, fjöldi einstaklinga í hóp. Síðan koma $n$ línur, ein fyrir hvern einstakling í hópnum, sem inniheldur eina heiltölu $0 < y_ i \leq 10^5$, tekjur $i$-ta einstaklingsins.

Úttak

Skrifið út Gini stuðul fyrir hópinn Úttakið er talið rétt ef talan er annaðhvort nákvæmlega eða hlutfallslega ekki lengra frá réttu svari en $10^{-6}$. Þetta þýðir að það skiptir ekki máli með hversu margra aukastafa nákvæmni talan eru skrifuð út, svo lengi sem hún er nógu nákvæm.

Stigagjöf

Hópur	Stig	Takmarkanir
1	50	$n \leq 10^3$
2	50	$n \leq 10^5$

Sample Input 1	Sample Output 1
5 100 100 100 100 100	0.00000000000000000

Sample Input 2	Sample Output 2
5 400 100 300 200 500	0.26666666666666666

Sample Input 3	Sample Output 3
10 1 1 1 1 10000 1 1 1 1 1	0.89910080927165548