Velocirráptor ruso P78006


Statement
 

pdf   zip

thehtml

Te dispones a tomar la montaña rusa cuando te das cuenta que un velocirráptor está corriendo en línea recta hacia ti. Por suerte, tienes una vía de escape: la propia montaña rusa. Sabes que el velocirráptor te podrá seguir por la vía, pero que no cabrá por el túnel de la montaña rusa. Empiezas a empujar el vagón por el andén, mientras el velocirráptor te persigue. Por razones obvias quieres montarte cuanto antes en el vagón: deseas conseguir la suficiente velocidad como para llegar hasta el túnel y deshacerte del velocirráptor, pero no quieres empujar más de lo estrictamente necesario por si te atrapa en el propio andén.

Conoces de memoria cada una de las subidas y bajadas que tiene la montaña rusa. Además, sabes que por cada metro en vertical que se sube, el vagón pierda una velocidad de K kilómetros por hora, mientras que por cada metro en vertical que baja, recupera la misma velocidad de K kilómetros por hora perdida (las leyes de la física no se cumplen a rajatabla en los parques de atracciones; si no, no tendría sentido pagar tanto por entrar a ellos). Sabes también que no se pierde velocidad por el rozamiento con la vía, y que es aceptable que el vagón tenga velocidad 0 durante algún momento del recorrido (con un pequeño impulso por tu parte el vagón seguiría avanzando hacia adelante) pero que en ningún momento puede tener velocidad negativa.

Entrada

La primera línea del juego de pruebas contiene el número de casos a resolver. Cada caso empieza con 3 enteros N, X y K en una línea, donde N es el número de tramos de la atracción, X es la coordenada x del punto donde se encuentra el túnel, y K es la velocidad en kilómetros por hora que se pierde (respectivamente, se gana) por cada metro subido (respectivamente, bajado) en vertical. Las siguientes N+1 líneas contienen N+1 pares de coordenadas (xi,yi), separados por un espacio, que describen los extremos de los N tramos rectos de los que se compone la atracción. Se cumple que (x1,y1) es siempre (0,0), y que los xi son estrictamente crecientes, es decir, xi < xi+1. Además, el túnel siempre coincide con el inicio de algún tramo de la montaña rusa, es decir, existe un punto xi con 1<iN tal que xi = X.

Salida

Para cada caso, escribe en una línea la velocidad mínima en kilómetros por hora con la que debes salir del andén para alcanzar el inicio del túnel, garantizando que durante todo el trayecto la velocidad del vagón es mayor o igual que 0.

Puntuación

  • TestA:  ‍ Pruebas con no más de 20 casos donde N ≤ 15 y X ≤ 1000.  ‍30 Puntos ‍
  • TestB:  ‍ Pruebas con no más de 20 casos donde N ≤ 25000 y X ≤ 106.  ‍70 Puntos ‍
Public test cases
  • Input

    5
    5 51 10
    0 0
    2 97
    51 11
    67 -85
    148 -116
    214 -68
    5 87 19
    0 0
    87 -79
    124 -170
    167 -221
    197 -146
    205 -230
    5 35 15
    0 0
    35 -33
    132 -10
    141 -64
    178 -97
    226 -126
    5 249 7
    0 0
    77 -46
    132 -96
    182 -107
    249 -184
    329 -212
    5 196 7
    0 0
    37 -7
    97 8
    183 40
    196 126
    280 58
    

    Output

    970
    0
    0
    0
    882
    
  • Input

    2
    2 10 7
    0 0
    10 0
    20 0
    4 30 7
    0 0
    10 10
    20 10
    30 0
    40 0
    

    Output

    0
    70
    
  • Information
    Author
    Ricardo Martin
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++