Introducción al problema

En este problema se debe implementar un programa para organizar los paquetes a distribuir un conjunto de paquetes a entregar en una ciudad.

Descripción del problema

Implementar un programa para resolver el siguiente problema.

Problema

La empresa Envíos S.A.S. lo contrata para que resuelva el problema de organizar los envíos a realizar en un día particular bajos las siguientes condiciones:

• - En el centro de acopio se encuentran P paquetes a distribuir organizados en M montones (un paquete sobre el otro), para ser cargados en C camiones. Cada paquete tiene asociado un identificador entero para facilitar su rastreo y la dirección de envío, expresada como dos coordenadas (x, y).

• - Se considera que la ciudad en la que se distribuirán los paquetes tiene un área rectangular con ancho A y largo L.

• - La ciudad se ha dividido en C regiones de manera uniforme así:

• - La división de las C regiones va de acuerdo a la siguiente imágen:

• - La región 1 inicia en las coordenadas (0,0) y la región C termina en las coordenadas (A, L).

• - Los límites de la región son inclusivos para el borde superior y el borde de la izquierda, y exclusivos para el borde inferior y el de la derecha.

• - Un camión se asigna para entregar los paquetes de una región particular.

• - Cada uno de los paquetes de los M montones se deben asignar a cada uno de los C camiones para su entrega.

• - Los paquetes a distribuir se deben organizar para su carga en los C camiones para su entrega de tal forma que los paquetes a entregar de últimos deben quedar al fondo del camión y los que se entreguen de primeros en la ruta sean los últimos en cargar.

• - Usted debe realizar un programa que recorra los M montones de paquetes que se encuentran apilados y haga la asignación de cada uno de los P paquetes a cada uno de los C camiones, de acuerdo con la región en la que se deben entregar.

• - Al final de toda la asignación, se deben imprimir en orden de carga los paquetes asignados a cada uno de los camiones de acuerdo con su región de la ciudad asignada.

• - El programa debe ayudarle a organizar los paquetes para su carga, por lo cual debe ponerlos en una cola para que sean cargados en el camión correspondiente, de tal manera que los expedientes que queden al frente de la cola sean los primeros a ser cargados son los últimos en ser entregados.

• - Suponga que el centro de acopio está ubicado en las coordenadas (0,0). También, suponga que cuando un camión llega a su región asignada, empieza a distribuir los paquetes en la esquina superior izquierda del rectángulo correspondiente a su región.

• - Use como criterio para la carga de los paquetes en un camión la distancia de Manhattan desde las coordenadas de la entrega hasta la esquina superior izquierda de la región particular. También, suponga que para la entrega de los paquetes un camión sigue una ruta moviéndose en “zig-zag” de izquierda a derecha y de arriba hacia abajo así:

Importante: el programa debe recibir la entrada por consola como se indica e imprimir la salida en el formato que se especifica.

Entrada

• - La primera línea tiene tres números enteros así: A, el ancho de la ciudad, L el largo de la ciudad y C el número de regiones en las que se divide la ciudad para asignar los paquetes al mismo número de camiones.

• - La segunda línea de la entrada debe contener dos números enteros: P, el cual representa la cantidad de paquetes y M, el número de montones en que están apilados los paquetes.

• - En la siguiente línea se debe leer la información de cada uno de los paquetes que está en el primer arrume de paquetes. Los datos de cada paquete son un entero con el identificador de rastreo y las dos coordenadas enteras donde debe entregarse. En otras palabras, esta primera línea contiene tripletas de números enteros: número de rastreo del paquete, coordenada x de entrega del paquete y luego está la coordenada y de entrega del paquete, todos separados por espacios. El orden en que aparecen los datos de los paquetes en la entrada corresponde al orden en que están apilados, primero aparece el que está en la parte superior del montón.

• - En la siguiente línea se incluye la especificación de los paquetes en el segundo arrume a través de tripletas de números enteros, de la misma forma que en la línea anterior.

• - A continuación vienen una cantidad de líneas como las dos anteriores necesarias para especificar los paquetes que están apilados hasta completar la información de los M montones.

Salida

La salida debe consistir de C líneas, de tal forma que cada línea indica los paquetes asignados a cada camión según la región asignada al camión. En cada línea, primero se incluye un entero con el identificador de la región, que va desde 1 hasta el número de regiones (igual al número de camiones). Luego en la misma línea se debe incluir una lista de números enteros con los número de rastreo de los paquetes asignados al camión correspondiente de acuerdo con su región. Estos números se deben imprimir en el orden en que los paquetes deben ser cargados en el camión de acuerdo con el orden de recorrido, desde el más lejano al más cercano, en el orden en que se van a poner en una cola para ser cargados.

Restricciones

• • \(1 \leq P \leq 10^5\)
• • \(1 \leq A,L \leq 10 ^ 6\)
• • \(1 \leq M, C \leq 100\)
• • TODAS las coordenadas son expresadas en números enteros.
• • Suponga que los camiones tienen espacio suficiente para cargar todos los paquetes asignados
• • Para implementar su solución, deberá implementar sus propias estructuras de datos de tipo: Pila, Cola, Listas, según sea su propuesta. No se pueden usar las librerías (bibliotecas) nativas del lenguaje de programación aplicado.

Ejemplos

4000 2000 4
15 2
3 100 100 4 1200 1300 2 3600 1800 5 400 500 13 500 400 11 3600 1500 15 200 800
10 300 1700 1 2500 400 6 700 600 8 2500 600 9 2400 1200 7 2500 900 12 700 1300 14 1300 1500

1 3 13 5 6 15
2 1 8 7
3 12 4 14 10
4 9 11 2