P16984 [NWERC 2018] Access Points

A well-known programming contest is considering a new way to position its teams. For the contest all $n$ teams have to be assigned some position $(x,y)$ in an infinitely-large gym hall. To keep a good overview of the teams the following strategy is chosen: All teams have been assigned a unique integer ID in the range $[1,n]$. Any two teams with IDs $i$ and $j$, where $i

The input consists of: - One line with one integer $n$ ($1 \le n \le 10^5$), the number of teams. - $n$ lines, the $i$th of which contains two integers $s_i,t_i$ ($1 \le s_i,t_i \le 10^6$), the location of the internet access point of team $i$. No two access points are at the same position.

Output the minimum total cost of all UTP cables required to connect the teams to their access points in an optimal legal layout. Your answer should have an absolute or relative error of at most $10^{-6}$.