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 {p0, …, pn−1} amb coordenades enteres pi = (xi, yi), cal calcular
| d∞(pi, pj) , |
on d∞(pi, pj) = max(| xi − xj |, | yi − yj |).
Entrada
L’entrada consisteix en diversos casos, cadascun amb n seguida dels n punts, tots diferents i amb coordenades entre 0 i 109. Podeu suposar 2 ≤ n ≤ 104.
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 Θ(n logn) amb una constant força baixa.
Input
2 2 3 4 10 4 0 0 0 1 1 0 1 1 3 1000000000 1000000000 0 1000000000 1000000000 0
Output
7 6 3000000000
- Author
- Manuel Torres
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++