Problema 5
Luchas
luchas.pas, luchas.c, luchas.cpp

Aconteció, en una pelea del legendario luchador “El Matemático”, que dejó tendidos a todos sus rivales por todo el ring, el réferi le pidió que los acomodara en ciertos lugares para poder recoger con mayor facilidad los restos de sus contrincantes. Estaba muy cansado el famoso luchador, por lo cual sólo podía cargar a un personaje en cada viaje.
El ring es similar al primer cuadrante del plano cartesiano, y la posición inicial de “El Matemático” es el origen. Por extrañas manías sólo le gusta caminar en dirección paralela a los ejes. ¿Cuál es la longitud del camino de longitud mínima que debe recorrer?

Problema
Dejar luchadores en ciertos lugares haciendo un recorrido de longitud mínima.

Entrada
El primer renglón tendrá la cantidad n (1 ≤ n ≤ 9), de luchadores por recoger. Los siguientes n renglones tendrán 4 enteros, los primeros dos serán la posición del luchador y los siguientes dos, las coordenadas a donde deben ser llevado ese luchador. Todos los números de la entrada estarán entre 0 y 32000 (inclusive).

Salida
Un único entero, la longitud mínima que tiene que recorrer “El Matemático” para llevar a todos los demás luchadores al lugar que se indica.

Ejemplo

entrada salida
2
5 4 5 6
9 7 0 5
27

Explicación de la salida: Parte de su esquina (0,0) y va por el luchador que se encuentra en (5,4), (recorre 9 unidades), lo lleva a la (5,6) (recorre 2 unidades), luego va por e luchador que se encuentra en la (9,7) (recorre 5 unidades) y lo lleva a la (0,5) (recorre 11 unidades). Recorrió en total 9 + 2 + 5 + 11 = 27.

 


Concurso: ICPC - 6 Concurso Interno de la Universidad Bonaterra. 26/Mayo/2006
Propuesto por: Pier Paolo Guillén Hernández
Ayuda: entradas, salidas, sugerencias
Soluciones: luchas.pas, luchas.c, luchas.cpp


World of πer