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,\dots ,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={\displaystyle \frac{\sum _{i=1}^n\sum _{j=1}^n|y_i-y_j|}{2\sum _{i=1}^n\sum _{j=1}^n{y}_i}}$$

Hér táknar $|x|$ algildi $x$: $|x|=x$ ef $x\ge 0$, en $|x|=-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\le {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\le {10}^3$
2	50	$n\le {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