optimizacion de cortes
Publicado por daniel castillo (1 intervención) el 22/06/2018 05:42:57
a pesar de que lo he pensado mucho, no se me ocurre como hacerlo, ayuda por favor, cualquier consejo, solucion, programa sirve, el problema dice lo siguiente
La tienda ”FACIL”, una empresa de Retail que vende materiales de construcci´on, herramientas, menaje de
hogar y muebles, entre otros; quiere contratar un buen ingeniero que le ayude en el dise˜no de sus nuevas puertas
de seguridad, las cuales se esperan sean grito y plata dada la sensaci´on de inseguridad existente en el pa´ıs.
Estas puertas cuentan con sensores instalados en los 4 lados de la puerta, donde cada par de sensores est´a
conectado por alambres. Si alguien abre la puerta, alguno de los sensores detectar´a la apertura y sonar´a una
alarma.
Sin embargo, el sistema tiene un peque˜no defecto de dise˜no. Un instruso podr´ıa intentar cortar los alambres
antes de abrir la puerta, pero, aunque no es imposible, es dif´ıcil realizar los cortes. Por tanto, mientras menos
cortes tenga que hacer un ladr´on m´as vulnerable ser´a la puerta.
As´ı, el problema consiste en determinar el m´ınimo n´umero de cortes requeridos para desactivar todas los
sensores. La figura muestra dos configuraciones de puertas (que m´as adelante veremos en los respectivos
ejemplos de entrada), donde las l´ıneas azules representan las conexiones entre los sensores y las l´ıneas rojas
representan los cortes m´ınimos que se deben realizar para cortar todos los alambres y desconectar la alarma.
Entradas:
Las entradas consisten en varios n´umeros. Tres enteros n, w y h correspondientes a la cantidad de sensores
instalados (1 ≤ n ≤ 106
) y las dimensiones de la puerta (1 ≤ w, h ≤ 108
). Luego vienen n tuplas de datos
que describen la ubicaci´on de los sensores. Cada tupla contiene 4 enteros x1, y1, x2 e y2 (0 ≤ x1, x2 ≤ w,
0 ≤ y1, y2 ≤ h) que indican que el alambre va desde (x1, y1) a (x2, y2). Cada alambre conecta la puerta por
diferentes lados de esta. Ning´un alambre puede ser anclado en una esquina y la ubicaci´on de todos los sensores
es distinta.
Salidas:
El programa debe calcular y desplegar la cantidad m´ınima de cortes realizados en l´ınea recta, que se inicien y
terminen en distintos lados de la puerta y que intersecten a todos los alambres de los sensores instalados.
Luego, debe desplegar las coordenadas de inicio y fin de los cortes realizados (indicando uno por l´ınea)
usando el mismo formato que en la entrada se utiliz´o para la ubicaci´on de los sensores, e.d., 4 enteros x1, y1,
x2 e y2 (0 ≤ x1, x2 ≤ w, 0 ≤ y1, y2 ≤ h) que indican que el corte va desde (x1, y1) a (x2, y2). La coordenada de
inicio o de t´ermino de un corte no puede estar a menos de 10−6 de ning´un sensor o esquina de la puerta.
Los cortes se pueden desplegar en cualquier orden.
La posici´on de inicio y fin de un corte puede ser desplegada en cualquier orden.
Si el problema tiene m´as de una soluci´on se debe desplegar s´olo una de ellas, cualquiera.
La tienda ”FACIL”, una empresa de Retail que vende materiales de construcci´on, herramientas, menaje de
hogar y muebles, entre otros; quiere contratar un buen ingeniero que le ayude en el dise˜no de sus nuevas puertas
de seguridad, las cuales se esperan sean grito y plata dada la sensaci´on de inseguridad existente en el pa´ıs.
Estas puertas cuentan con sensores instalados en los 4 lados de la puerta, donde cada par de sensores est´a
conectado por alambres. Si alguien abre la puerta, alguno de los sensores detectar´a la apertura y sonar´a una
alarma.
Sin embargo, el sistema tiene un peque˜no defecto de dise˜no. Un instruso podr´ıa intentar cortar los alambres
antes de abrir la puerta, pero, aunque no es imposible, es dif´ıcil realizar los cortes. Por tanto, mientras menos
cortes tenga que hacer un ladr´on m´as vulnerable ser´a la puerta.
As´ı, el problema consiste en determinar el m´ınimo n´umero de cortes requeridos para desactivar todas los
sensores. La figura muestra dos configuraciones de puertas (que m´as adelante veremos en los respectivos
ejemplos de entrada), donde las l´ıneas azules representan las conexiones entre los sensores y las l´ıneas rojas
representan los cortes m´ınimos que se deben realizar para cortar todos los alambres y desconectar la alarma.
Entradas:
Las entradas consisten en varios n´umeros. Tres enteros n, w y h correspondientes a la cantidad de sensores
instalados (1 ≤ n ≤ 106
) y las dimensiones de la puerta (1 ≤ w, h ≤ 108
). Luego vienen n tuplas de datos
que describen la ubicaci´on de los sensores. Cada tupla contiene 4 enteros x1, y1, x2 e y2 (0 ≤ x1, x2 ≤ w,
0 ≤ y1, y2 ≤ h) que indican que el alambre va desde (x1, y1) a (x2, y2). Cada alambre conecta la puerta por
diferentes lados de esta. Ning´un alambre puede ser anclado en una esquina y la ubicaci´on de todos los sensores
es distinta.
Salidas:
El programa debe calcular y desplegar la cantidad m´ınima de cortes realizados en l´ınea recta, que se inicien y
terminen en distintos lados de la puerta y que intersecten a todos los alambres de los sensores instalados.
Luego, debe desplegar las coordenadas de inicio y fin de los cortes realizados (indicando uno por l´ınea)
usando el mismo formato que en la entrada se utiliz´o para la ubicaci´on de los sensores, e.d., 4 enteros x1, y1,
x2 e y2 (0 ≤ x1, x2 ≤ w, 0 ≤ y1, y2 ≤ h) que indican que el corte va desde (x1, y1) a (x2, y2). La coordenada de
inicio o de t´ermino de un corte no puede estar a menos de 10−6 de ning´un sensor o esquina de la puerta.
Los cortes se pueden desplegar en cualquier orden.
La posici´on de inicio y fin de un corte puede ser desplegada en cualquier orden.
Si el problema tiene m´as de una soluci´on se debe desplegar s´olo una de ellas, cualquiera.
Valora esta pregunta
0