|
ACM - Universidad Autonoma de Puebla |
Entrada: pozo.in
Salida: estándar
Máxima memoria: 32 MB
Tiempo límite: 20 segundos
¿Habías oído hablar acerca de una persona que viviera en una plataforma petrolera en medio del océano? Jerónimo es un multimillonario que tiene cientos de pozos petroleros, todos cercanos entre sí a medio del océano. Él vive en una de sus plataformas petroleras, es una persona muy excéntrica y paranoica, piensa que muchos de sus competidores quieren matarlo, sueña lo mismo cada noche y nos dio esta información, sacada de una pagina de su diario:
“Esta ves en mi sueño, logre subir a mi avión, pensaba que la bomba lo afectaría pero no fue así, despegué sin ningún problema, pero en el trayecto se acabo el combustible, logre recargarlo antes que las ondas de destrucción me alcanzaanr, pero se me volvió ha acabar y esta vez no pude recargarla a tiempo, por lo que el avión calló en picaday desperté.”
A partir del sueño, él a comprado detectores, para que en dado caso de que exista dicha bomba sea detectada con anticipación, también a comprado un avión que despegue y aterrice en un tiempo despreciable, y por último, dotó a cada plataforma petrolera con un sistema automático de sumistración de combustible para su avión, dicho sistema carga a su avión en un tiempo t constante. Pero necesita que le ayudes a determinar un camino para alcanzar una plataforma petrolera segura, ya que él sabe que las olas tienen que parar en algún momento, y además quiere llegar lo antes posible, por que necesita estar lo menos posible en el aire, para que sus enemigos no lo detecten.
Ya que con sus detectores que compro el tiene mucha información, como la velocidad que viajan las olas y cosas por el estilo,el te dará todo lo necesario para que le ayudes. Las distancias de una plataforma a otra tal como de la ondas de las olas que se acercan , se medirán como la distancia Euclidiana.
Para cada caso de prueba recibirás en la primera línea el entero n ( 1 ≤ n ≤ 500 ) que es el número de plataformas que tiene Jerónimo, en las siguientes n líneas, hay dos enteros xi y yi (0 ≤ xi, yi ≤ 100) que representan la posición en el mapa donde está la i-esima plataforma, en la siguiente línea sigue con tres enteros l,t y tv (1 ≤ l ≤ n, 0 ≤ t ≤ 1 0, 1 ≤ tv ≤ 100) donde l indica la plataforma donde se encuentra Jerónimo, t el tiempo que su avión tarda en recargar combustible, y tv la distancia que el avión puede recorrer sin volver a cargar combustible, en la siguiente línea están cuatro enteros: xo, yo,to y tt (1 ≤ xo, yo ≤ 100, 1 ≤ to ≤25 , 1 ≤ tt ≤ 200 ) donde xo y yo son las coordenadas de donde se detecto la bomba que origina las olas, to es el la distancia que recorre una ola por cada unidad de tiempo y tt es el tiempo que las olas tardan con una altura peligrosa para las plataformas, los casos de prueba terminan cuando n = 0.º
Nota: El avión solo recorre una unidad de distancia por cada unidad de tiempo.
Nota: Puedes estar seguro que el número de casos de prueba no pasan de 100.
Para cada caso de prueba deberás imprimir dos líneas.
P Q |
Primera línea. P es el numero de plataformas que tiene que visitar, para que llegue a un lugar a salvo, en el mínimo de tiempo posible, y Q es el tiempo que tardo en llegar a una plataforma segura, con precisión de tres decimales. En dado caso que no exista la posibilidad de sobrevivir debes imprimir en P y Q un -1 Segunda línea. Debes imprimir las plataformas que tiene que visitar para llegar a su destino, si existe más de una forma de llegar, debes proyectar la que empiece con los números menores. En dado caso de no encontrar ninguna forma de ayudarlo, debes imprimir “Buena Suerte”. |
Ejemplo de entrada |
Ejemplo de salida |
|---|---|
7 |
3 4.650
|