Este desafío se basa en otro desafío similar. Debido a que encontrar el empaque más eficiente de los rectángulos es NP-difícil (es decir, su solución es fácil de verificar pero difícil de encontrar), este desafío es mucho más fácil que este aquí

Este desafío

Dado un montón de rectángulos, averigua si llenan o no un espacio rectangular sin espacios ni superposiciones.

Entrada

La entrada puede ser de dos formas, una de las cuales conlleva una penalización de puntuación.

El primero: contiene una lista de sublistas, cada una con una longitud 4. Esta lista contiene 4 enteros que son las coordenadas de vértices opuestos. Como todos los rectángulos serán horizontales / verticales, no hay ambigüedad en cuanto a dónde está el rectángulo. Cada sublista contendrá cuatro enteros, que, en orden, son la coordenada x del primer vértice, la coordenada y del primer vértice, la coordenada x del segundo vértice y la coordenada y del segundo vértice.

El segundo: contiene cuatro listas de enteros con la misma longitud. Las cuatro listas representan las diferentes coordenadas. Si imagina la opción de entrada 1 como una matriz, la entrada aquí es solo la transposición de la matriz. Esta entrada lleva una +20%penalización de byte.

Salida

Salida simple de verdad / falsedad.

Especificaciones

Si hay un rectángulo con área 0 (es decir, x1 == x2 || y1 == y2), ignore este rectángulo (entonces [0 0 1 1], [2 2 3 2]es válido). Esta especificación está en su lugar para que sea más difícil para las personas simplemente obtener los valores mínimo / máximo x / y.

x1 <= x2y y1 <= y2no siempre son verdad Si x1 > x2 || y1 > y2, el rectángulo no es un rectángulo de área cero; más bien, ocupa el espacio rectangular entre (x1, y1)y (x2, y2).
Las coordenadas pueden ser negativas, en cuyo caso aún ocupan el espacio entre las coordenadas.
El rectángulo superior izquierdo no siempre está en (0, 0); por lo tanto, el espacio rectangular que se llena no necesariamente tiene su esquina superior izquierda en (0, 0).
(Gracias a @xnor por señalar estas ambigüedades)

Especifique cómo desea su entrada y cómo se representará su salida.

Puntuación

La puntuación es el tamaño del código en bytes, más una penalización de bytes, si corresponde. El puntaje más bajo al 15 de diciembre gana.

Casos de prueba

0 0 1 2
1 0 3 1 ==> true
1 1 3 2

0 0 2 2
0 0 1 1 ==> false
0 0 0 0

0 0 1 1
2 2 2 2 ==> true
0 1 2 1

¡Buena suerte, feliz golf!

JavaScript (ES6), 249 bytes

with(Math)a=>!(a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]).filter(g=([l,t,r,b])=>(r-l)*(b-t))).reduce((s,b)=>s-g(b),g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))

Nota: Para usar esto, evalúelo como una cadena y asigne el resultado a una variable, o inserte la asignación después de with(Math). Explicación:

with(Math)a=>!(Traer miny maxen alcance.
a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b])Normalice las coordenadas
.filter(g=([l,t,r,b])=>(r-l)*(b-t)))Elimine los rectángulos vacíos, también defina una función para calcular el área
.reduce((s,b)=>s-g(b),Reste las áreas de todos los rectángulos
g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))del área del cuadro delimitador
>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))y verifique que no se superpongan rectángulos.

Mathematica, 194 bytes

(r=Select[#,(#-#3)(#2-#4)&@@#>0&];m={#~Min~#3,#2~Min~#4,#~Max~#3,#2~Max~#4}&@@Transpose@r;b=Boole[(x-#)(x-#3)<0&&(y-#2)(y-#4)<0]&;Integrate[(Plus@@(b@@@r)-b@@m)^2,{x,#,#3}&@@m,{y,#2,#4}&@@m]<1)&

Una versión sin golf:

1  (r = Select[#1, (#1 - #3) (#2 - #4) & @@ #1 > 0 &]; 
2   m = {Min[#1, #3], Min[#2, #4], Max[#1, #3], Max[#2, #4]} & @@ Transpose[r]; 
3   b = Boole[(x - #1) (x - #3) < 0 && (y - #2) (y - #4) < 0] &;
4   Integrate[
5     (Plus @@ (b @@@ r) - b @@ m)^2 ,
6     {x, #1, #3} & @@ m ,
7     {y, #2, #4} & @@ m
8   ] < 1
9  ) &

La línea 1 define rcomo el conjunto de rectángulos no triviales de la entrada dada. (Hay una gran cantidad de& @@ cosas que suceden en este código; eso es solo para que podamos usar #1,#2,#3,#4los cuatro elementos de una lista en lugar de #[[1]],#[[2]],#[[3]],#[[4]]). Luego, la línea 2 define mlas coordenadas del rectángulo más pequeño que delimita a todos los que figuran en la lista r; entonces, si los rectángulos de entrada forman un mosaico con un rectángulo grande, ese rectángulo grande debe ser m.

La línea 3 define la función bque, cuando se aplica a un cuádruple que representa un rectángulo, produce una función de dos variablesx y yque es igual a 1 si el punto (x,y)está dentro del rectángulo y 0 si no lo está. La línea 5 produce muchas de estas funciones, una para cada rectángulo en r(todas sumadas) y una última para el rectángulo grande m(restado); esa complicada función de dos variables es al cuadrado.

La clave, en este punto, es que esa función de dos variables es idénticamente 0 si los rectángulos pequeños forman un mosaico con el rectángulo grande, pero tendrá algunos valores positivos si se superponen dos rectángulos pequeños, o algunos valores negativos (antes del cuadrado) si alguna parte del rectángulo grande no está cubierto. Detectamos esto al integrar literalmente (!) La función de dos variables sobre el rectángulo grande (los límites de integración se dan en las líneas 6-7): si obtenemos 0, entonces el mosaico fue perfecto, y si obtenemos un valor positivo , entonces hubo un problema en alguna parte. Como todo lo que se ve es un número entero, guardamos un byte final al usarlo en < 1lugar de == 0en la línea 8.

(Creo que es bastante divertido que podamos explotar la capacidad de Mathematica para hacer cálculos para resolver este problema combinatorio).