|
|
2397 - Collecting Luggage |
||||
|
|
|||||
La recolección de su equipaje después de un vuelo puede
ser muy lejos de lo trivial. Maletas y bolsas debe aparecer en una cinta
transportadora, y cientos de pasajeros luchan por una buena atalaya de
encontrar y recuperar sus pertenencias. Recientemente, en el Aeropuerto de
Narita la autoridad ha decidido hacer este proceso más eficiente. Antes de
rediseñar su reclamación de equipaje en zonas, que necesitan un programa de
simulación para determinar cómo se comportan los pasajeros promedio en la
recogida de su equipaje. Esta simulación asume que los pasajeros siempre toman
un camino de línea recta para llegar a segmentos de su equipaje en la menor
cantidad de tiempo.
Para este problema, una cinta transportadora sigue el modelo como un simple
polígono. Una pieza de equipaje aparece en algún momento de la cinta
transportadora y, a continuación, se mueve a lo largo de la cinta
transportadora a una velocidad constante. Un pasajero inicialmente se coloca en
algún momento fuera de la cinta transportadora polígono. Tan pronto como la
pieza de equipaje aparece, el pasajero se mueve a una velocidad constante (que
es mayor que la velocidad de la pieza de equipaje) con el fin de recoger el
equipaje. El pasajero del camino, que no podrá cruzar el cinturón
transportador, pero pueden tocar, el pasajero pone en la misma posición que el
movimiento de pieza de equipaje en la menor cantidad de tiempo.
En la siguiente figura, la cinta transportadora se representa como un polígono
abcdef. El equipaje se inicia en la esquina superior izquierda (Punto A) y se
mueve en dirección de todo el polígono como se muestra con las flechas. El
pasaje comienza en el punto P se mueve y en el camino que él y pone el equipaje
en el mismo lugar (punto H en la figura) en el menor lapso de tiempo. El
pasajero del camino se muestra por una flecha roja. Esta cifra corresponde a la
primera muestra de entrada.
Input
La entrada se compone de uno o más casos de prueba se
describen escenarios de recogida de equipajes. Un escenario descripción
comienza con una línea que contiene un único número entero N (3
N100), el número de vértices de la cinta transportadora polígono. Esto
es seguido de N líneas, cada uno con un par de enteros xi , yi (| xi|,| yi|10000) dando las
coordenadas de los vértices del polígono en el orden contrario. El polígono es
simple, es decir, no cortar a sí mismo y no va a tocar. El polígono descripción
es seguida por una línea que contiene dos enteros px , py (| px|,| py|10000), las
coordenadas de la posición inicial del pasajero. La última línea de la
descripción contiene dos enteros positivos VL and VP
(0 < VL < VP10000), que son
la velocidad de los equipajes y los pasajeros, respectivamente. Todas las
coordenadas están dadas en metros, y las velocidades están dadas en metros por
minuto.
Se puede suponer que el pasajero se coloca fuera de la cinta transportadora
polígono. El equipaje se moverá en dirección en torno a la cinta
transportadora, a partir del primer vértice del polígono.
La entrada es denunciada por una línea que contenga un solo número entero cero.
Output
Para cada caso de prueba, imprimir una línea que contiene
el número de caso de prueba (comenzando por 1), seguido por el mínimo tiempo
que le toma a los pasajeros para llegar al equipaje. Utilice el formato
mostrado en la muestra de salida (con minutos y segundos, separados por dos
puntos), redondeado al segundo más cercano. El valor para los segundos deben
imprimirse en un campo de la anchura de dos (relleno con ceros principales si
es necesario).
Sample Input
6 0 40 0 0 20 0 20 20 40 20 40 40 120 40 70 100 40 0 10 0 10 10 0 10 100 100 10 11 0
Sample Output
Case 1: Time = 1:02 Case 2: Time = 12:36