# Star Wars

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.

::: center
![image](xw.eps){width="10.0cm"}
:::

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 \le n \le 50$, i que totes les coordenades són
enters no més grans que $10^6$ 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.

::: center
![image](sw.eps){width="14.0cm"}
:::

## Informació del problema

Autoria: Salvador Roura

Generació: 2026-01-25T11:33:03.062Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
