De fondo

Con la llegada de las estaciones de trabajo de alta velocidad gráfica, CAD (Diseño por medio de computadores) y otras áreas (CAM, diseño VLSI) queda el hecho del incremento del uso de computadoras. Uno de los problemas con el dibujo de imágenes es la eliminación de líneas ocultas -- líneas opacadas por otras partes de un trazo.

El problema

Tienes que diseñar un programa para ayudar a un arquitecto a dibujar la línea del horizonte de una ciudad determinando las ubicaciones de los edificios en la ciudad. Para hacer aceptable el problema, todos los edificios son rectangulares y parten de un fondo común (en la ciudad ellos están edificados en el mismo plano). La ciudad es también vista como dos dimensiones. Una construcción esta especificada por un triple ordenado tex2html_wrap_inline149 donde tex2html_wrap_inline151 y tex2html_wrap_inline153 son las coordenadas izquierda y derecha, respectivamente, del edificio i y tex2html_wrap_inline157 es la altura del edificio. En el diagrama de abajo los edificios se muestran a la izquierda con edificios triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) , la línea del horizonte, mostrada a la derecha, está representada por la secuencia (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0).

figure26

La entrada

La entrada es una secuencia de edificios triples. Todas las coordenadas de de los edificios son enteros positivos menores que 10,000 y al menos un edificio y máximo 5,000 edificios en el archivo de entrada. Cada edificio triple esta en una línea sola en el archivo de entrada. Todos los enteros están separados por uno o más espacios. Los triples estan ordenados por Li, la coordenada izquierda x del edificio, así los edificios con menor cordenada izquierda x esta primero en el archivo de entrada.

La salida

La salida debe consistir de el vector que describe la línea del horizonte como se muestra en el ejemplo citado arriba. En el vector de la línea del horizonte tex2html_wrap_inline183 , los tex2html_wrap_inline185 tal que i es un número par representado una línea horizontal (altura). El tex2html_wrap_inline185 tal que i es número impar representa una línea vertical (coordenada x). El vector de la línea del horizonte debe representar la "trayectoria" tomada, por ejemplo, por un error comenzando en la mínima coordenada x y viajando horizontalmente y verticalmente de todas las líneas que definen la línea del horizonte. Así la última entrada en el vector de la línea del horizonte debe ser un cero. Las coordenadas deben estar separadas por un espacio en blanco.

Ejemplo de entrada

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

Ejemplo de salida

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0