Distància infinit P86818

El club de “Paseíllos extremos FME” és conegut per haver arribat des de Barcelona fins a Terrassa, Montserrat i Mataró en un sol dia (o una sola nit). El seu gran objectiu és anar caminant fins a França, on volen visitar $n$ llocs d’interès. Durant la passejada debaten com de dispersos estan aquests llocs entre si, i decideixen que una bona mètrica seria calcular la distància infinit entre cada parell de llocs. Podeu ajudar-los?

Formalment: Donats $n$ punts $\{p_0, \dots, p_{n-1}\}$ amb coordenades enteres $p_i = (x_i, y_i)$, cal calcular $$\sum_{0 \le i < j < n} d_{\infty}(p_i, p_j) ,$$ on $d_{\infty}(p_i, p_j) = \max(\vert x_i - x_j \vert, \vert y_i - y_j \vert)$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ seguida dels $n$ punts, tots diferents i amb coordenades entre 0 i $10^9$. Podeu suposar $2 \le n \le 10^4$.

Sortida

Per a cada cas, escriviu la suma de les distàncies infinit entre tots els parells de punts.

Pista

La solució esperada té cost $\Theta(n \log n)$ amb una constant força baixa.