El juego de trenes P41202

Juan tiene un nuevo juego de trenes. Este tiene varios tramos rectos que se pueden unir para formar pistas más largas. Estos se unirán siempre de tal modo que la pista sea contínua y todos los tramos formen una recta con diferentes desniveles (el juego no contiene tramos curvos, estos vienen en la expansión). El juego también tiene vagones que Juan puede lanzar desde un punto de la vía con la velocidad que él desee. María, la hermana de Juan, ha puesto los tramos formando una vía y reta a Juan a lanzar un vagón desde el comienzo de la vía de tal modo que este llegue a una posición con la mínima velocidad.

Juan ha observado que por cada centímetro que suben los coches, estos pierden A mm/s de velocidad por la fuerza de la gravedad, mientras que por cada centímetro que bajan, estos ganan A mm/s de velocidad. Además, por cada metro de pista recorrida, debido al rozamiento con la pista, estos pierden B mm/s de velocidad. Juan quiere que el vagón se quede parado en la posición que le ha indicado María, que está a una distancia de X cm en horizontal desde el comienzo de la vía. Juan quiere saber la mínima velocidad con la que tiene que lanzar el vagón para que llegue al punto indicado por María.

Entrada

La entrada consisitirá en varios juegos de prueba. La primera línea contendrá un número que indicará el número de juegos de prueba a resolver. Cada juego de prueba comenzará con 4 números A, B, X y N, en este orden, en una línea, dónde N será el número de tramos de la pista y serán enteros. Las siguientes N+1 líneas contendrán N+1 pares de punto de la forma (x_i,y_i) con x_i e y_i medidos en milímetros y siendo enteros, donde (0,0) será el primero punto y los x_i serán estrictamente crecientes, es decir, x_i < x_i+1. Estos puntos representan una pista de N tramos rectos unidos. Se sabe que N ≤ 1000 y que |y_i| ≤ 100. Salida

Para cada caso, escribe en una línea la parte entera superior de la velocidad mínima en mm/s con la que se ha de lanzar el vagón para que alcance el punto indicado por María.

Pista: Tener en cuenta, que cuanto más rápido lanzes el vagón desde el origen, más lejos llegará este. Por lo tanto, se puede saber que si el vagón no llega a la posición P con una velocidad determinada, se le ha de lanzar con más velocidad.

Autor: Ricardo Martín

La solucion se puede encontrar iterando por la pista hasta llegar a la posicion X.

PROBLEMAS DOUBLE En caso de llegar a un pico con velocidad 0, como decidimos si sigue hacia abajo o no?? Solucion = no puede haber picos... si os parece..