Star Wars P59249

Luke Skywalker ha de fugir de Tatooine, el planeta on viu, per anar al planeta Dagobah, on rebrà les lliçons del mestre Yoda. Lamentablement, el seu caça de tipus Ala-X només té autonomia per volar entre planetes que es trobin a distància d o menys. Encara pitjor, l’Imperi disposa de m destructors estel·lars, cadascun dels quals pot impedir exactament una comunicació directa entre qualsevol parell de planetes que esculli.

En funció de m, quina és la mínima d que assegura a Luke poder anar de Tatooine a Dagobah, independentment de quines comunicacions directes impedeixi l’Imperi?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de planetes n, seguit de n ‍triplets (x, y, z) amb les coordenades dels n planetes. El primer planeta donat és Tatooine, i l’últim és Dagobah. Suposeu 2 ≤ n ≤ 50, i que totes les coordenades són enters no més grans que 10⁶ en valor absolut. No hi ha dos planetes al mateix lloc. Considereu l’univers prou gran com per poder tractar els planetes com punts unidimensionals.

Sortida

Per a cada cas, i per a cada valor de m entre 0 i n−2, escriviu amb tres decimals la mínima d que permet a Luke fugir de les forces imperials. Els jocs de proves no tenen problemes de precisió amb els decimals. Escriviu una línia amb 20 ‍asteriscs al final de cada cas.

Per exemple, considereu el primer cas del sample. Si l’Imperi no té cap destructor, una autonomia d=4 és suficient, perquè es pot anar del primer planeta al segon, i després del segon al tercer. En canvi, si l’Imperi té un destructor, cal autonomia d=5 per poder viatjar també directament entre el primer i el tercer planetes, i així assegurar sempre una ruta, independentment de quina sigui la connexió directa que controli el destructor.