Star Wars P59249


Statement
 

pdf   zip

thehtml

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 106 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.



Public test cases
  • Input

    3
    0 0 0
    0 4 0
    0 4 3
    
    10
    1000 74 43
    18 -20 0
    1234 9876 1000
    -432 -543 -654
    98 49 7
    23 33 42
    -100 -200 -300
    500 -600 999
    9876 753 -468
    -842 -1028 144
    
    2
    -1000000 -1000000 -1000000
    1000000 1000000 1000000
    

    Output

    0: 4.000
    1: 5.000
    ********************
    0: 1019.867
    1: 1197.198
    2: 1332.817
    3: 1372.716
    4: 1436.070
    5: 1707.958
    6: 2148.853
    7: 10882.189
    8: 11132.822
    ********************
    0: 3464101.615
    ********************
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++