En este desafío, se le dan dos rectángulos superpuestos, y necesita calcular los rectángulos creados al eliminar uno del otro.

Por ejemplo, si quita el rectángulo rojo del negro:

Terminas con uno de los siguientes dos conjuntos de rectángulos:

También deberá manejar lo siguiente:

Para ser más explícito:

• Ingresará las coordenadas de dos rectángulos, A y B.
• Debe generar la menor cantidad de rectángulos no superpuestos que cubran toda el área de A sin B. Se permite cualquier cobertura posible
• Las coordenadas rectangulares se pasan como 4 enteros. Puede pasarlos en dos pares (que representan los dos puntos de esquina), o como una tupla / lista de 4 enteros. Sus entradas y salidas deben ser consistentes.
• A y B no necesariamente se superpondrán o tocarán, y cada uno tendrá un área de al menos 1

Casos de prueba:

[(0 0) (5 5)] [(3 4) (8 7)]   -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)]  -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)]    #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)]   ->    #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)]   -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)]  #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)]   -> [(1 5) (7 8)]  #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)]   -> [(4 1) (10 5)] [(4 7) (10 9)]  #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)]     -> [(1 1) (8 6)]   #Only possible output

Este es un código de golf , ¡así que haga su código lo más corto posible!

Python 2 , 375 360 345 343 bytes

from itertools import*;P=product
def f(S,M):(l,t),(r,b)=S;(L,T),(R,B)=M;u,v,x,y=(L>=r)+(l<L),(T>=b)+(t<T),(R>=r)+(l<R),(B>=b)+(t<B);return[S]if v==y!=1or u==x!=1else[list(p(p(*zip(*(S+M))),repeat=2))[[43,197,6,199,9,231,142,229,53,189,134,181][int(i,36)]]for i in '38,491,258,2058,8,4B,28,208,7,41,27,461,,4,2,4A'.split(',')[u+2*v+4*x+8*y-12]]

Pruébalo en línea!

EDICIONES: -15 de sugerencias de @notjagan; otro -15 al volver a codificar la matriz de rectángulos de solución en formato int36 y una tabla de búsqueda corta; otro -2 al reemplazar el producto con p según @musicman.

Una función que toma dos rectángulos, cada rect es una tupla de ((izquierda, arriba), (derecha, abajo)); devuelve una lista de los rectángulos resultantes.

La estrategia básica:

     |     |
 0,0 | 1,0 | 2,0
-----A-----+-----
     |     |
 0,1 | 1,1 | 2,1
-----+-----B-----
     |     |
 0,2 | 1,2 | 2,2
     |     |

En el diagrama anterior, los puntos A y B son la esquina superior izquierda y la inferior derecha, respectivamente, del rectángulo 'Fuente' (el primer rectángulo).

Encontramos la ubicación de cada una de las partes superior izquierda (u,v)e inferior derecha (x,y)del rectángulo 'Máscara' en esa cuadrícula.

Si ambos puntos están en la primera o última columna; o primera o última fila; entonces no hay superposición; y podemos devolver solo la fuente rect.

De lo contrario, quedan 16 casos; por ejemplo, el primer ejemplo del OP es el caso en el que podemos etiquetar(1,1),(2,2) . Cada caso se puede asignar a un conjunto de rectángulos resultantes cuyas esquinas siempre son coordenadas con valores horizontales en los rectángulos de origen a la izquierda, a la derecha o en los rectángulos de máscara a la izquierda, a la derecha; y de manera similar para los valores verticales, la parte superior, inferior o las máscaras de la fuente.

Por ejemplo, para el (1,1),(2,2)caso, los rectángulos serían ((l,t),(T,r))y ((l,T),(R,b)), donde l,t,r,by L,T,R,Bson los lados izquierdo, superior, derecho e inferior de los rectángulos Fuente y Máscara, respectivamente.

Por lo tanto, podemos crear una tabla de búsqueda que asigne las coordenadas al conjunto de todas esas combinaciones posibles (que es de lo que se trata el product(product(*zip(*)))bit) a un conjunto de rectángulos que se deben proporcionar para cada uno de los casos (que, después de una descompresión de golf) , es de lo que trata el resto de la lista).

JavaScript, 115 bytes

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=a[i]=n,p)).filter(x=>x)

versión superpuesta:

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=n,p)).filter(x=>x)

Entrada en el siguiente formato: f([1,1,8,8])([0,6,9,9])

Denote la entrada como ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

Si se cumple alguna de las siguientes condiciones, devuelve el primer rectángulo tal como está:

• x3> x2
• x4 <x1
• y3> y2
• y4 <y1

de otra manera

• Si x1 <x3 <x2 entonces generamos un rectángulo ((x1, y1), (x3, y2)); y establecer x1: = x3
• Si x1 <x4 <x2 entonces generamos un rectángulo ((x4, y1), (x2, y2)); y establecer x2: = x4
• Si y1 <y3 <y2 entonces generamos un rectángulo ((x1, y1), (x2, y3)); y establezca y1: = y3
• Si y1 <y4 <y2 entonces generamos un rectángulo ((x1, y4), (x2, y2)); y establezca y2: = y4

Java, 268 bytes

class W{public static void main(String[]z) {int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};for(i=0;i<4;i+=1){for(j=0;j<4;j+=1){a[j]=Integer.parseInt(z[y[i*4+j]]);}if(a[0]<a[2] && a[1]<a[3]){for(j=0;j<4;j+=1){System.out.println(String.valueOf(a[j]));}}}}}

Sin golf

class W{
    public static void main(String[]z) {
        int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};

        for(i=0;i<4;i+=1){
            for(j=0;j<4;j+=1){
                a[j]=Integer.parseInt(z[y[i*4+j]]);
            }
            if(a[0]<a[2] && a[1]<a[3]){
                for(j=0;j<4;j+=1){
                    System.out.println(String.valueOf(a[j]));
                }
            }
        }
    }
}

Pase la entrada como argumentos. Ejemplo

java -jar W.jar 0 0 5 5 3 4 8 7

Python 2 , 272 bytes

lambda((a,b),(c,d)),((e,f),(g,h)):[([([[(a,b),(e,min(h,d))]]+[[(g,max(b,f)),(c,d)]]*2+[[(max(a,e),b),(c,f)]]*4+[[(a,h),(min(c,g),d)]])[m-1]for m in M&{1,2,4,8}]if M&{0}else[(a,b),(c,d)])for M in[{(x<e)*1+(x>g)*2+(y<f)*4+(y>h)*8 for x in range(a,c)for y in range(b,d)}]][0]

Pruébalo en línea!

Esto funciona probando cada celda dentro del primer rectángulo para izquierda = 1, superioridad = 4, rectitud = 2 e inferioridad = 8 w / r a la otra, y ORing el resultado. Si el otro no se cruza = 0 con el primero, entonces se devuelve el original, de lo contrario se devuelve alguna combinación de un corte izquierdo, un corte derecho, un corte superior y un corte inferior, con acomodación para la superposición.